二分查找算法总结

发表于 分类于
本文字数： 3.4k 阅读时长 ≈ 3 分钟

二分查找或二分搜索（binary search），是一种在有序数组中查找某一特定元素的搜索算法。必须满足以下特征：

  • 存储在数组中
  • 有序排列

如果是用链表存储的，就无法应用二分查找了，因为链表不能通过下标随机访问其元素。

本文介绍基本的二分查找及其各种变体。

1.基本二分查找

基本二分查找的搜索过程是从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果中间元素大于目标值，则在数组小于中间元素的那一半中查找；如果中间元素小于目标值，则在数组大于中间元素的那一半查找。如果在某一步数组为空，则代表找不到。二分查找算法每一次比较都会使搜索范围缩小一半。

基本二分查找的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int basic_binary_search(const vector<int>& nums, int target)
{
    int left = 0, right = nums.size()-1;
    int mid;
    while (left <= right){
        mid = left + (right - left)/2;
        //target在左边，改右边界
        if (target < nums[mid])
            right = mid - 1;
        //target在右边，改左边界
        else if (target > nums[mid])
            left = mid + 1;
        else
            return mid;
    } 
    return -1;
}

2. 各种变体

二分查找除了基本的查找某个元素的位置之外，还有很多的变体。比如查找第一个大于target的元素位置，这经常用于寻找要插入的位置；反过来，也会查找第一个比target小的元素的位置。有时也会查找某个元素在数组中的上下界，也就是查找不大于target的最后一个元素的位置或是查找不小于target的第一个元素的位置。最后还会出现数组中有多个target元素时，需要查找第一次或最后一次出现target元素的位置。

因此，如下分成了六种变体，在编写相应的二分查找算法的代码时，需要注意的就是判断条件以及返回值的问题。不多说，先看代码：

变体1：查找第一个大于target的元素位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int find_first_greater(const vector<int>& nums, int target)
{        
    int left = 0, right = nums.size()-1;
    int mid;
    while (left <= right){
        mid = left + (right - left)/2;
        if (target < nums[mid])
            right = mid - 1;
        else
            left = mid + 1;
    }    
    if (left < nums.size())
        return left;
    return -1;
}
变体2：查找最后一个小于target的元素位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int find_last_less(const vector<int>& nums, int target)
{
    int left = 0, right = nums.size()-1;
    int mid;
    while (left <= right){
        mid = left + (right - left)/2;
        if (target <= nums[mid])
            right = mid - 1;
        else
            left = mid + 1;
    }
    if (right >= 0)
        return right;
    return -1;
}

与标准库中 upper_bound 函数功能一致。

变体3：查找第一个大于等于target的元素位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int find_first_greater_equal(const vector<int>& nums, int target)
{
    int left = 0, right = nums.size()-1;
    int mid;
    while (left <= right){
        mid = left + (right - left)/2;
        if (target <= nums[mid])
            right = mid - 1;
        else
            left = mid + 1;
    }
    if (left < nums.size())
        return left;
    return -1;
}

与标准库中 lower_bound 函数的功能是一样的。

变体4：查找最后一个小于等于target的元素位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int find_last_less_equal(const vector<int>& nums, int target)
{
    int left = 0, right = nums.size()-1;
    int mid;
    while (left <= right){
        mid = left + (right - left)/2;
        if (target < nums[mid])
            right = mid - 1;
        else
            left = mid + 1;
    }
    if (right >= 0)
        return right;
    return -1;
}
变体5：查找第一个等于target的元素位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int find_the_first(const vector<int>& nums, int target)
{
    int left = 0, right = nums.size()-1;
    int mid;
    while (left <= right){
        mid = left + (right - left)/2;
        if (target <= nums[mid])
            right = mid - 1;
        else
            left = mid + 1;
    }
    if (left < nums.size() && nums[left] == target)
        return left;
    return -1;
}
变体6：查找最后一个等于target的元素位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int find_the_last(const vector<int>& nums, int target)
{
    int left = 0, right = nums.size()-1;
    int mid;
    while (left <= right){
        mid = left + (right - left)/2;
        if (target < nums[mid])
            right = mid - 1;
        else
            left = mid + 1;
    }
    if (right >= 0 && nums[right] == target)
        return right;
    return -1;
}

3. 总结

看以上循环部分的代码都有一种结构：

1
2
3
4
5
6
7
8
while (left <= right){
    mid = left + (right - left)/2;
    if (target ➀ nums[mid])
        right = mid - 1;
    else
        left = mid + 1;
}
return ➁;

不同的地方有两个：

  • 循环体内部的判断条件：if (target ➀ nums[mid])

    ➀所在的位置的比较符号是 < 或 <= 。不存在大于或大于等于的情况。

  • 返回值：return ➁;

    ➁所在位置返回值是 left 或 right。

循环的终止条件都是 left > right。

不同变体的情况下，➀➁处的取值如下表：

变体 ➀ ➁
查找第一个大于target的元素位置 < left
查找最后一个小于target的元素位置 <= right
查找第一个大于等于target的元素位置 <= left
查找最后一个小于等于target的元素位置 < right
查找第一个等于target的元素位置 <= left
查找最后一个等于target的元素位置 < right

根据上表，再根据问题的一些特点可以得出以下一些规律：

  • 查找第一个（大于、大于等于、等于）target的元素位置，也就是找左边界，返回 left。
  • 查找最后一个（小于、小于等于、等于）target的元素位置，也就是找右边界，返回 right。

另外，其实变体 5、6 在元素存在于数组中时，与变体3、4是一样的解法。