二分查找及其变种

二分查找是非常基础的算法，日常应用和面试中都极常见。其思想简单，不再赘述，但想要写好二分查找，也并不是那么容易的。

图来自《算法（第4版）》

• 经典算法（array是升序序列，下同）

    int binarySearch(int target, int[] array) {
        int low = 0, high = array.length - 1;
        // 注意<=
        while (low <= high) {
            // 防止low + high溢出
            int mid = low + (high - low) / 2;
            if (array[mid] < target) {
                low = mid + 1;
            } else if (array[mid] > target) {
                high = mid - 1;
            } else { // =
                return mid;
            }
        }
        return -1;
    }

• 如有多个等于target的值，查找第一个相等的值，否则返回-1

    int binarySearchFirstEq(int target, int[] array) {
        int low = 0, high = array.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (array[mid] < target) {
                low = mid + 1;
            } else { // >=
                high = mid - 1;
            }
        }
        if (array[low] == target) {
            return low;
        }
        return -1;
    }

为什么不仍然使用经典算法，最后加一个for循环来找到符合条件的元素呢？
如果序列很长，且相等值有很多重复的话，算法效率有可能会因此由O(logn)退化为O(n)。

• 如有多个等于target的值，查找第一个相等的值，否则查找第一个大于target的值

    int binarySearchFirstGte(int target, int[] array) {
        int low = 0, high = array.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (array[mid] < target) {
                low = mid + 1;
            } else { // >=
                high = mid - 1;
            }
        }
        return low;
    }

• 查找第一个大于target的值

    int binarySearchFirstGt(int target, int[] array) {
        int low = 0, high = array.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (array[mid] <= target) {
                low = mid + 1;
            } else { // >
                high = mid - 1;
            }
        }
        return low;
    }

同样地，既然可以查找“第一个”，那么就可以查找“最后一个”。

• 如有多个等于target的值，查找最后一个相等的值，否则返回-1

    int binarySearchLastEq(int target, int[] array) {
        int low = 0, high = array.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (array[mid] <= target) {
                low = mid + 1;
            } else { // >
                high = mid - 1;
            }
        }
        if (array[high] == target) {
            return high;
        }
        return -1;
    }

• 如有多个等于target的值，查找最后一个相等的值，否则查找最后一个小于target的值
• 查找最后一个小于target的值
  参考上面的思路，相信这两个也就不难做了。

总之，弄清楚array[mid]与target之间的大小关系，以及最终需要返回low/mid/high三者之间的哪一个值，问题就可迎刃而解。