二分查找的一些思考

发表于 更新于 分类于 阅读次数： 本文字数： 2.1k 阅读时长 ≈ 4 分钟

二分查找的流程

先来看一个问题：

力扣704 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

这题的暴力解很容易想到，就是依次遍历，直到找到target，否则则返回-1。这样做的时间复杂度为O(n)

暴力解忽略了题目中有序数组的条件。在这种条件下，使用二分查找能节省大量的时间。

输入 nums = [5,7,7,8,8,10], target = 8

我们使用两个指针：左指针和右指针分别指向数组的0下标和len(nums)-1 (这里采用的是闭区间写法)

每次的循环中，我们取left和right区间中间的数(这里记为nums[mid])，将nums[mid]同target进行比较。

这时候有三种情况：

  1. nums[mid] > target 此时right应该缩小 即right = mid - 1
  2. nums[mid] < target 此时left应该前进 即left = mid + 1
  3. nums[mid] = target 此时返回mid即可

由此，我们就可以得到下面这段代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size()-1;
        while (l <= r) {
            int mid = l + (r - l) / 2; // 这里为了防止溢出
            if (target > nums[mid]) l = mid + 1;
            else if (target < nums[mid]) r = mid - 1;
            else return mid;
        }
        return -1; // 没有找到结果直接返回-1就好
    }
};

二分查找时间复杂度和空间复杂度

由于我们每次都是在中间选取，所以二分查找的时间复杂度应该为O(log 2)

二分查找算法中，因为只用了几个变量作为参数，所以空间复杂度为O(1)

二分查找的要求

是否能进行二分查找，要满足两个条件：

  1. 数组为顺序存储 (链表不适用)
  2. 数组中元素有序

数组为顺序存储这个条件比较好理解。如果题目给定的是一个链表的话，因为链表不能够直接从下标获取到元素，而是要通过遍历得到，所以对链表使用二分查找显然不是十分有效率。

数组中元素有序，这个条件的重点在有序。这里的有序当然不仅仅包含，单调递增或是单调递减，这里的有序可以理解为广义上的有序。例如力扣852. 山脉数组的峰顶索引，就不是按照所有元素单调性的有序进行存储，但是只要我们可以根据nums[mid]来确定数组元素的大小，就可以认定为有序。

四种情况的讨论

在二分查找中，抓住循环不变量很关键：

以704为例

[0, l-1] x < target
[r+1, n-1] x > target

在二分查找中，其实有四种情况：

  1. >=
  2. >
  3. <=
  4. <

我们来看这道题目 力扣34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

这道题目其实相当于让我们求第1和3种情况

我们先来求第三种情况 <=

1
2
3
4
5
6
7
8
9
int lower_bound(vector<int>& nums, int target) {
    int l = 0, r = nums.size()-1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (target > nums[mid]) l = mid + 1;
        else r = mid - 1;
    }
    return l;
}

事实上，<= 是能和其他三种情况相互转换的。

< target 可转化为 <= (target) - 1
> target 可转化为 >= (target + 1)
>= target 可转化为 (<= target + 1) - 1

那么，本题就可以先计算出<=的情况 再由此推出>=的情况

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res{-1, -1};
        int start = this->lower_bound(nums, target);
        // 如果没找到target
        if (start == nums.size() || nums[start] != target) {
            return res;
        }
        // >= target 可转化为 (<= target + 1) - 1
        int end = this->lower_bound(nums, target+1) - 1;
        res[0] = start; res[1] = end;
        return res;
    }

特别感谢

感谢灵神，给我带来的启发qwq