二分查找

什么是二分查找算法

二分查找算法是在有序序列中查找某一特定元素的查找算法，所谓 “二分”，即：每次查找可以排除一半的元素，所以时间复杂度为 O(log2^n)，因此也被称为折半查找（指的是对半排除元素），对数查找（对数指的时间复杂度中的对数）。

二分查找算法

普通二分查找

算法步骤

假设存在长度为 n 的 升序 数组 A[]，查找元素 target 是否存在。

注意： 数组降序也是可以的，二分查找一般情况下是升序或降序，符合特定规则的升序和降序也是可以的，比如：两段升序的拼接，这里以升序为例进行讲解。

（0）首先，初始化 left = 0, right = n，表示查找的区间为 [ left，right)，最开始时，查找的区间为 [0, n)；

（1）计算 left 和 right 的中间节点，中间节点的下标为 mid = (left + right) /2 。

（2）然后，判断 target 与 中间节点值 A[ mid ] 的大小；

（3）如果 target = A[ mid ] ，说明在数组 A 中找到了元素 target，结束查询；

（4）如果 target < A [ mid ] ，说明，target 并不在数组 A 的区间 [mid, right) 中，因为数组 A 是升序数组，所以 target 应该在区间 [left，mid) 中，所以 left 值不变，让 right = mid；

（5）否则，target > A[ mid ]，说明，target 在区间 [ mid + 1，right) 中，同样，是因为数组 A 是升序数组，所以 right 的值不变，让 left = mid + 1；

（6）重复步骤 （1）~（5），直到查找到 target 或 left >= right 为止，如果出现 left >= right（这时区间为空，没有元素了），则表示数组 A 中没有找到 target 。

动图演示

来看一下动图演示，假设升序数组 A[] = {1, 3, 5, 7, 9, 11, 13}，查找 target = 1，如下所示：

在上述动图中，一共查找了三次，第三次 mid = 0，便查找到了 target = 1，具体查找步骤如下所示：

（1）、最开始查找范围为 [0, 7)，left = 0, right = 7, 计算 mid = 3；

（2）、缩小查找范围为 left = 0, right = 3，查找范围为 [ 0, 3)，重新计算 mid = 1；

（3）、再次缩小查找范围 left = 0, right = 1，查找范围为 [0, 1)，重新计算 mid = 0；

（4）、A[ mid = 0 ] = 1 ，查找到 target。

上述就是二分查找数组 A 中 1 的过程。

代码实现

int binarySearch(int A[], int n, int target){
    int left = 0, right = n;
    // 查找的区间为 [left, right)
    while(left < right){ 
        // 更好的方法是：mid = left + (right - left) / 2 能防止溢出
        int mid = (left + right) / 2; 
        if(A[mid] == target) return mid;
        else if(A[mid] > target) right = mid;
        else left = mid + 1;
    }
    // 查找不到
    return -1; 
}

二分查找下界

算法步骤

假设存在长度为 n 的 升序 数组 A[]，数组中存在重复的元素，要查找元素 target 的最小下标。如下所示：

（0）首先，初始化 left = 0, right = n，表示查找的区间为 [ left，right)，最开始时，查找的区间为 [0, n)；

（1）计算 left 和 right 的中间节点，中间节点的下标为 mid = (left + right) /2 。

（2）然后，判断 target 与 中间节点值 A[ mid ] 的大小；

（3）如果 A[ mid ] >= target，因为查找的是下界，所以 target 在区间 [ left, mid) 区间还可能存在，所以进一步缩小空间，将查找区间缩小为 [left, mid)，所以 left 值不变，让 right = mid；

（4）否则，A[ mid ] < target，说明 target 在区间 [ mid + 1，right) 中，因为数组 A 是升序数组，所以 right 的值不变，让 left = mid + 1；

（5）重复步骤 （1）~（4），直到跳出 while 循环；

（6）如果 right 等于 n 或 A [ right ] != target ，则表示未查找到 target，否则 A[ right ] = target，right 为数组 A 中值为 target 的最小下标；

动图演示

来看一下动图演示，假设升序数组 A[] = {1, 3, 3, 3, 9, 11, 13}，查找 target = 3，如下所示：

在上述动图中，一共查找了三次，第三次 mid = 0 结束查找（代码中是 left == right 跳出 while 循环）right 指向的值等于 target，具体查找步骤如下所示：

（1）、最开始查找范围为 [0, 7)，left = 0, right = 7, 计算 mid = 3；

（2）、因为[0, 3) 中可能还存在 target，缩小查找范围为 left = 0, right = 3，新查找范围为 [ 0, 3)，重新计算 mid = 1；

（3）、因为[0, 1) 中可能还存在 target，再次缩小查找范围 left = 0, right = 1，新查找范围为 [0, 1)，重新计算 mid = 0；

（4）、left 重新计算后，left == right，结束查找，right 指向的值等于 target。

代码实现

int lowerSearch(int A[], int n, int target){
    int left = 0, right = n;
    while(left < right){
        int mid = left + (right - left)/2;
        if(A[mid] >= target) right = mid;
        else left = mid + 1;
    }
    if(right == n || A[right] != target)
        return -1;
    return right;
}

注意： 需要判断 right 是否是指向 target，因为查找数组中可能就不存在 target。

二分查找上界

算法步骤

假设存在长度为 n 的 升序 数组 A[]，数组中存在重复的元素，要查找元素 target 的最大下标。如下所示：

（0）首先，初始化 left = 0, right = n，表示查找的区间为 [ left，right)，最开始时，查找的区间为 [0, n)；

（1）计算 left 和 right 的中间节点，中间节点的下标为 mid = (left + right) /2 。

（2）然后，判断 target 与 中间节点值 A[ mid ] 的大小；

（3）如果 A[mid] > target，所以 target 在区间 [ left，mid) 中，所以缩小空间，将查找区间缩小为 [left, mid)，所以 left 值不变，让 right = mid；

（4）否则，A[ mid ] <= target，说明 target 在区间 [ mid + 1，right) 中还可能存在，因为数组 A 是升序数组，所以 right 的值不变，让 left = mid + 1；

（5）重复步骤 （1）~（4），直到跳出 while 循环，left --，因为 left 指向的永远是比 target 大的值的下标；

（6）如果新的 left 等于 n 或 A [ left ] != target ，则表示未查找到 target，否则 A[ left ] = target，right 为数组 A 中值为 target 的最小下标；

动图演示

来看一下动图演示，假设升序数组 A[] = {1, 3, 3, 3, 9, 11, 13}，查找 target = 3，如下所示：

在上述动图中，一共查找了三次，第三次 mid = 4 结束查找（代码中是 left == right 跳出 while 循环）left - 1 指向的值等于 target，具体查找步骤如下所示：

（1）、最开始查找范围为 [0, 7)，left = 0, right = 7, 计算 mid = 3；

（2）、因为[4, 7) 中可能还存在 target，缩小查找范围为 left = 4, right = 7，新查找范围为 [ 4, 7)，重新计算 mid = 5；

（3）、因为[4, 5) 中可能还存在 target，再次缩小查找范围 left = 4, right = 5，新查找范围为 [4, 5)，重新计算 mid = 4；

（4）、left 重新计算后，left == right，结束查找，left - 1 指向的值等于 target。

代码实现

int upperSearch(int A[], int n, int target){
    int left = 0, right = n;
    while(left < right){
        int mid = left + (right - left)/2;
        if(A[mid] > target) right = mid;
        else left = mid + 1;
    }
    left--;
    if(left == n || A[left] != target)
        return -1;
    return left;
}

注意: left 是查找值更大值的下标，所以让 left --，还需要判断一下 left 所指向的值是否是 target，因为可能在查找数组中就不存在 target。

复杂度分析

时间复杂度

每次查找都是排除一半的情况（缩减一半），相当于每次都除以 2，假设长度为 n，查找次数为 x，则 2^x <= n ，x 约等于 log2^n，所以时间复杂度为 O(log2^n)。

空间复杂度

通常二分查找并不需要额外的辅助空间，所以空间复杂度为 O(1)。