二分查找以及变体

标准二分查找

使用场景

1. 排序的数组（排序，且支持随机读取）
2. 不大不小的数据， 大了的话，数组太大，木有那么大的连续空间，小了话，基本没有优势。
3. 因为二分查找能够减少比较次数，所以如果比较操作比较复杂的话，那么不管数组大小都优先二分查找。

 public static int binarySearchStandard(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        while (end >= start) {
            int mid = start + ((end - start) >> 1);
            if (nums[mid] < target) {
                start = mid + 1;
            } else if (nums[mid] > target) {
                end = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

代码注意事项：

1. 循环条件 end >= start
2. mid = start + ((end - start) >> 1) 防止 采用 （end + start) / 2可能的越界行为。
3. start = mid + 1； end = mid - 1；防止死循环。

变体：

1. 找出有序数组里，第一个等于target的元素下标
2. 找出有序数组里，最后一个等于target的元素下标

    public static int binarySearchFirstOne(int[] array, int target) {
        int start = 0;
        int end = array.length - 1;
        while (end >= start) {
            int mid = start + ((end - start) >> 1);
            if (array[mid] == target) {
                if (mid == 0 || array[mid - 1] != target) return mid;
                end = mid - 1;
            } else if (array[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return -1;

    }


    public static int binarySerarchLastOne(int[] array, int target) {
        int start = 0;
        int end = array.length - 1;
        while (end >= start) {
            int mid = start + ((end - start) >> 1);
            if (array[mid] == target) {
                if (mid == (array.length - 1) || array[mid + 1] != target) return mid;
                start = mid + 1;
            } else if (array[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return -1;
    }

变体

1. 找出有序数组里，第一个大于target的元素下标
2. 找出有序数组里，最后一个小于target的元素下标

    public static int binarySearchFirstGreaterOne(int[] array, int target) {
        int start = 0;
        int end = array.length - 1;
        while (end >= start) {
            int mid = start + ((end - start) >> 1);
            if (array[mid] > target) {
                if (mid == 0 || array[mid - 1] <= target) return mid;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return -1;


    }

    public static int binarySearchLastLessOne(int[] array,int target) {
        int start = 0;
        int end = array.length - 1;
        while (end >= start) {
            int mid = start + ((end - start) >> 1);
            if (array[mid] < target) {
                if (mid == (array.length - 1) || array[mid + 1] >= target) return mid;
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return -1;
    }

上述的写法，很容易理解，不用想各种的边界条件，简直就是棒棒哒，核心就是对每次可能的候选值进行判断，而不是一窝蜂跳出循环之后在判断。