二分查找：加倍缩小搜索区间

二分思路和模版

二分这种算法我们在很小的时候肯定就已经接触过了，很多智力题都可以用二分来解决。比如

1. AB2地之间的电线断了，如何快速确定电线在哪里断了？我们每次都是到一段电线的中间去找
2. 给12个小球和一个天平，其中一个小球的质量和其他的小球不同，称3次把那个质量不同的小球找出来

二分算法最主要的应用场景就是判断指定数在有序数组中是否存在，注意是有序数组

二分算法可以算作是双指针的一种经典应用。二分算法的模版如下所示，其中变化的部分就是确定搜索区间的过程，我们要根据搜索区间的不同来赋不同的值。

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (...) {
    	// 就是 int mid = (left + right) / 2;
    	// 这样写是为了防止溢出
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...;
        } else if (nums[mid] < target) {
            left = ...;
        } else if (nums[mid] > target) {
            right = ...;
        }
    }
    return -1;
}

以最常见的场景为例，给一个nums数组，判断target在nums数组中是否存在，如果存在则返回数组下标，不存在则返回-1

// 模版一
public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    return -1;
}

为什么while里面是<=，而不是<？

这里就涉及到一个搜索区间的概念。 如果是<=，则搜索区间是[left, right]（2端都是闭区间），此时数组中的所有数都能被搜索到 如果是<，则搜索区间是[left, right)（前闭后开区间），数组中的最后一个数不能被搜索到。 例如，有如下一个数组{1, 2, 3, 4}，我们查找4在这个数组中是否存在，如果是<=，则会返回3。如果是<，则会返回-1

基于最基本的二分算法，会扩展出很多变种，如。

查找 nums 数组中最早出现的值为 target 的下标，查找 nums 数组中最晚出现的值为 target 的下标

其实这个问题套用我们上面的模版也能解决，先找到值为 target 的下标。

如果是找最早出现的，则接着向前遍历，如果是找最晚出现的，则接着向后遍历

寻找左边界的二分查找

// 模版2
// 寻找左侧边界的二分搜索
public int leftSearch(int[] nums, int target) {
    int result = -1, left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (nums[mid] == target) {
            right = mid - 1;
            result = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

当我们找到指定值的时候，并不直接返回下标，而是将右区间更新为mid - 1，这样当找到指定值时，还能一直找最早出现的。

寻找右边界的二分查找

寻找右边界的二分搜索的过程和搜索左边界的原理类似

// 模版3
// 寻找右侧边界的二分搜索
public int rightSearch(int[] nums, int target) {
    int result = -1, left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (nums[mid] == target) {
            left = mid + 1;
            result = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

常见面试题

掌握了这几个模版，当遇到二分查找的题目，我们都能快速应对

在排序数组中查找元素的第一个和最后一个位置

题目来源：LeetCode34

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]

示例1

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例2

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

我们跑一个寻找左边界的模版和寻找右边界的模版即可

搜索二维矩阵 II

题目来源：LeetCode240

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 数组有序即可二分，我们对每一行二分查找即可（当然你也可以按列二分查找）

public boolean searchMatrix(int[][] matrix, int target) {
    for (int i = 0; i <= matrix.length - 1; i++) {
        if (matrix[i][0] > target) {
            return false;
        }
        int left = 0;
        int right = matrix[i].length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (matrix[i][mid] == target) {
                return true;
            } else if (matrix[i][mid] > target) {
                right = mid - 1;
            } else if (matrix[i][mid] < target) {
                left = mid + 1;
            }
        }
    }
    return false;
}