在一个有序的序列中，先比较目标值和数组中最中间的值是否相等，如果不相等 断是大于该值还是小于，大于则从中间处和尾部继续比较拆分，一次可排除一半的值。当然，有个大前提是在有序的数据中进行查找。

二分查找法的递归写法

/**
 * @author cv大魔王
 * @version 1.0
 * @description 二分查找法
 * @date 2022/10/26
 */
public class BinarySearch {

    private BinarySearch() {}

    /**
     * 二分查找法-递归实现
     * @param arr    数组
     * @param target 要查找的数据
     */
    public static <E extends Comparable<E>> int searchR(E[] arr, E target) {
        return searchR(arr, 0, arr.length - 1, target);
    }

    // target是要寻找的数
    private static <E extends Comparable<E>> int searchR(E[] arr, int l, int r, E target) {
        if (l > r) {
            return -1; //递归终止条件
        }
        int mid = l + (r - l) / 2; // mid是一组数据的中间数
        // 如果mid=target,代表找到了
        if (arr[mid].compareTo(target) == 0) {
            return mid;
        }
        // 如果mid<target则去右边继续找
        if (arr[mid].compareTo(target) < 0) {
            return searchR(arr, mid + 1, r, target);
        }
        // 如果mid>target则取左侧继续找
        return searchR(arr, l, mid - 1, target);
    }
}

二分查找法非递归实现

public class BinarySearch {

    private BinarySearch() {}

    /**
     * 二分查找法-非递归实现
     * @param arr    数组
     * @param target 要查找的数据
     */
    public static <E extends Comparable<E>> int search(E[] arr, E target) {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (arr[mid].compareTo(target) == 0) {
                return mid;
            }
            if (arr[mid].compareTo(target) < 0) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return -1;
    }
}

二分查找法变种-查找数组中大于target的第一个元素索引

例如0,1,2,2,3,3,4,4,5,6,7查找3返回索引6，也就是值4

public class BinarySearch {
    public static <E extends Comparable<E>> int upper(E[] data, E target) {
        int l = 0, r = data.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (data[mid].compareTo(target) <= 0) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
}

二分查找法变种-查找数组中相同元素中的索引最大值

例如1,1,3,3,5,5,7,7如果查找5则返回索引5，如果查找6则返回索引6，数组中没有6返回大于6的第一个元素的索引，也就是7的索引。

public class BinarySearch {
    public static <E extends Comparable<E>> int ceil(E[] data, E target) {
        // 借助upper函数进行实现
        int upper = upper(data, target);
        if (upper - 1 >= 0 && data[upper - 1].compareTo(target) == 0) {
            return upper - 1;
        }
        return upper;
    }
}