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

前言

二分查找的思想是简单易懂的，但是在具体实现的时候能被一些细节给逼疯。今天学习了一下二分查找相关的知识与小细节，听取同学的推荐，参考了大神“灵茶山艾府”的教学视频。

下面就以一道算法题为例子，来写一下二分查找的方法。但这篇博客我会不局限于这道题，尽量去着笔于二分查找的算法本身。

原题描述

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

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

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

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

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

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

示例 3：
输入： nums = [], target = 0
输出：[-1,-1]

提示： 0 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
nums 是一个非递减数组
-10⁹<= target <= 10⁹

解答

方法一：固定套路

思想

其实这道题从有序数组和O(log n)时间复杂度来看，很显然需要用到二分查找。

也就是需要用二分查找找到目标元素target出现的第一个位置和最后一个位置。

二分查找在实现的时候，根据左右边界开闭区间的不同，有三种实现方式：闭区间[l, r]、左开右闭(l, r]、开区间(l, r)。

我这里就用闭区间的方式来做，但是任何方式其实都是可以的的。

对于查找target的第一个位置，其实查找的就是>= target的第一个元素，在这里将查找>= target的函数记作findNotLess()。

但是在找到之后需要判断一下找到的位置是不是合法（因为如果这个数组元素都比target小，那么找到的位置是超出了数组边界的）；

还需要判断找到的位置是不是target（如果数组中不存在target，那么可能找到的是例如target+1这样的比target还要大的元素）。

像下图所示的例子。

如果经过判断发现，target存在数组中，并且找到了第一个出现的位置，那么如何找target的最后一个的位置？

答：找最后一个target其实就需要找到> target的第一个元素的位置，然后把这个位置-1即可。

也就相当于去找>= (target+1)的位置，然后将找到的下标-1，就得到了最后一个target的位置。（因为经过刚刚的判断，target一定存在，那么找到>= (targe+1)的位置，它左边一定是最后一个target）

可以发现，在找最后一个target时，用的是一种偷懒的方法来实现的，我把这种方式称作一种固定套路。

因此，在非递减顺序排列的int数组中，可以在这里进行一下拓展和总结：

1. 查找>= target的第一个位置，直接刚刚所说的findNotLess(target)方法；
2. 查找> target的第一个位置，可以转换成查找>= target+1，也就是findNotLess(target+1)；
3. 查找< target的最后一个位置，可以转换成查找>= target的第一个位置，然后将找到的下标减一。也就是findNotLess(target)-1
4. 查找<= target的最后一个位置，可以转换成查找> target的第一个位置再减一。二次转换成查找>= target+1的第一个位置再减一，也就是findNotLess(target+1)-1

注意：
上述查找时，在查找大于或大于等于一个数的时候，都是查找的第一个位置。
在查找小于或小于等于一个数的时候，都是查找的最后一个位置。
这是因为在非递减排序数组中，查找大于某个数的最后一个数是没意义的，一定在数组的最后面。
同样的，查找小于某个数的第一个数也是没意义的，一定是数组的开头。

代码实现

C++代码如下

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        int start = findNotLess(nums, target);
        if(start == n || nums[start] != target)
            return {-1, -1};
        int end = findNotLess(nums, target+1)-1;
        return {start, end};
    }
    int findNotLess(vector<int>&nums, int target){
        int n = nums.size();
        int l = 0, r = n-1;
        while(l <= r){
            int mid = l + (r-l)/2;  // 防止溢出的计算方式
            if(nums[mid] >= target)
                r = mid-1;  // r+1 都是大于等于target
            else
                l = mid+1;  // l-1都是小于target
        }
        return r+1; // 返回的是大于等于target的第一个数的下标
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

复杂度分析

时间复杂度

每次都将任务拆分成了之前的一半，O(logn)

空间复杂度

没有额外的空间开销，O(1)

方法二：灵活应用

思想

灵活应用的时候就是不仅仅只用方法一中的FindNotLess()函数，在查找出现的最后一个target的时候，通过更改函数中的比较方式来进行实现。
也就是下面这一部分：

if(nums[mid] >= target)
	r = mid-1;  // r+1 都是大于等于target
else
	l = mid+1;  // l-1都是小于target
1
2
3
4

在上述代码中，这个部分是使得r+1都是>=target，l-1都是<target。用这种方式，在结束的时候r+1的位置就是第一个target（假设target存在数组中）

我们需要改成l-1都是<=target，r+1都>target，这样结束的时候l-1的位置就是最后一个target。修改过后的代码见下。

代码实现

C++代码如下
其中find_left()函数就是上面的findNotLess()函数。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        int start = find_left(nums, target);
        if(start == n || nums[start] != target)
            return {-1, -1};
        int end = find_right(nums, target);
        return {start, end};
    }

    int find_right(vector<int> &nums, int target){
        int n = nums.size();
        int l = 0, r = n-1;
        while(l <= r){
            int mid = l + (r-l)/2;
            if(nums[mid] <= target)  // 注意这个地方的不同！！！
                l = mid+1;
            else
                r = mid-1;
        }
        return l-1;  // 返回的是<=target的最后一个数
    }

    int find_left(vector<int>&nums, int target){
        int n = nums.size();
        int l = 0, r = n-1;
        while(l <= r){
            int mid = l + (r-l)/2;
            if(nums[mid] >= target)
                r = mid-1;  // r+1 都是大于等于target
            else
                l = mid+1;  // l-1都是小于target
        }
        return r+1; // 返回的是大于等于target的第一个数的下标
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

复杂度分析

时间复杂度

O(logn)

空间复杂度

O(1)