二分查找算法详解（C++实现，图文并茂）

某大型娱乐节目在进行猜数游戏，主持人会在女嘉宾的手心写一个 10 以内的正整数，让男嘉宾猜该数是几，女嘉宾只能提示男嘉宾猜的数是大了还是小了，仅有 3 次猜数机会。你有没有办法以最快的速度猜出来呢？

从问题的描述来看，若有 n 个数，则在最坏情况下需要猜 n 次才能猜成功。其实完全没必要一个一个地猜，因为这些数是有序的，所以可以每次都猜中间的数：

• 若猜的数比中间的数小，则在前半部分查找；
• 若猜的数比中间的数大，则在后半部分查找。

这种算法被称为二分查找算法。

二分查找实现步骤

例如，一维数组 a[] 存储了有序序列，请在该数组中查找元素 x 的位置：
1) 初始化。令 l=0，r=n-1，分别指向数组中第一个元素和最后一个元素的下标。

2) 若 l>r，则算法结束，否则 mid=(l+r)/2，mid 指向查找范围内中间元素的下标。若数据较大，则为避免 l+r 溢出，可写为 mid=l+(r-l)/2。

3) 若 x=a[mid]，则查找成功，算法结束；若 x<a[mid]，则令 r=mid-1，在前半部分查找；否则令 l=mid+1，在后半部分查找，转向第 2 步。

二分查找完美图解

例如，在有序序列（5，8，15，17，25，30，34，39，45，52，60）中查找元素 17。


1) 初始化。l=0，r=10，计算 mid=(l+r)/2=5。


2) 将 x 与 a[mid] 做比较。x=17，a[mid]=30，x<a[mid]，令 r=mid-1，在前半部分查找，查找范围缩小到 [0，4]。计算 mid=(l+r)/2=2。


3) 将 x 与 a[mid] 做比较。x=17，a[mid]=15，x>a[mid]，令 l=mid+1，在后半部分查找，查找范围缩小到 [3，4]。计算 mid=(l+r)/2=3。


4) 将 x 与 a[mid] 做比较。x=a[mid]=17，查找成功，返回下标 mid（mid=3）。

二分查找算法实现

1) 非递归算法的实现如下：

int BinarySearch(int x) { // 二分查找
    int l=0, r=n-1;
    while(l<=r) {
        int mid=(l+r)/2; // mid 为查找范围的中间值
        if(x==a[mid]) // 查找成功
            return mid;
        else if(x<a[mid]) // 在前半部分查找
            r=mid-1;
        else // 在后半部分查找
            l=mid+1;
    }
    return -1;
}

2) 递归算法的实现如下。递归算法有自调用问题，需要增加两个参数 l 和 r 来标记查找范围的开始位置和结束位置。

int recursionBS(int l, int r, int x) { // 二分查找，递归算法
    if(l > r) // 递归结束条件
        return -1;
    int mid = (l + r) / 2; // 计算 mid 值
    if(x == a[mid]) // 查找成功
        return mid;
    else if(x < a[mid]) // 在前半部分查找
        return recursionBS(l, mid - 1, x);
    else // 在后半部分查找
        return recursionBS(mid + 1, r, x);
}

二分查找算法分析

1) 时间复杂度

若用 T(n) 表示对 n 个有序元素进行二分查找的时间复杂度，则分情况讨论如下：

• 当 n=1 时，需要比较一次，T(n)=O(1)。
• 当 n>1 时，将待查找元素和中间位置的元素做比较，时间复杂度为 O(1)。若不相等，则需要在前半部分或后半部分查找，查找范围缩小了一半，时间复杂度变为 T(n/2)。

• 递推求解：

• 递推最终的查找范围为 1，令n=2^x，则 x=logn。

二分查找的非递归算法和递归算法查找的方法一样，时间复杂度均为 O(logn)。

2) 空间复杂度

二分查找的非递归算法，变量占用了一些辅助空间，空间复杂度为 O(1)。

二分查找的递归算法，除使用了一些变量外，还使用了栈实现递归调用。在递归算法中，每次递归调用都需要一个栈空间来存储。

假设原问题的规模为 n：

• 首先将其分解为两个规模为 n/2 的子问题，对这两个子问题并不是每个都要求解，只会求解其中之一，因为与查找范围的中间值做比较后，要么在前半部分查找，要么在后半部分查找；
• 然后把规模为 n/2 的子问题继续分解为两个规模为 n/4 的子问题，选择其一进行求解；
• 继续分治下去，在最坏情况下会分治到只剩一个数值，从根到叶子所经过的节点，每层求解一个子问题，直到最后一层，如下图所示。

若递归调用最终的查找范围为 1，即 n/2x=1，则 x=logn。假设阴影部分是查找路径，一共经过了 logn 个节点，递归调用了 logn 次。递归算法使用的栈空间为递归树的深度，二分查找的递归算法的空间复杂度为 O(logn)。