【面试经典 150 | 二分查找】在排序数组中查找元素的第一个和最后一个位置

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

• Tag：介绍本题牵涉到的知识点、数据结构；
• 题目来源：贴上题目的链接，方便大家查找题目并完成练习；
• 题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
• 解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
• 知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【数组】【二分查找】

题目来源

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

题目解读

方法一：二分查找

对于有序数组中搜索指定元素问题，我们应该优先想到二分查找方法。题目有要求解法的时间复杂度必须为 $O(logn)$，那本题基本确定需要使用二分查找法解题。

思路

我们只需要写出一个函数找出数组中 target 第一次出现的位置。使用二分查找轻松实现。还有一些实现细节，见代码中的注释。

代码

class Solution {
public:
    // 【闭区间写法】找出 nums[i] >= target 的最小的 i
    int lower_bound(const vector<int>& nums, int target) {

        int left = 0, right = nums.size() - 1;
        while (left <= right) {     // 区间不为空
            // 注意指针的指向变化
            int mid = left + ((right - left) >> 1);
            if (nums[mid] < target) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return left;
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        int start = lower_bound(nums, target);
        if (start == nums.size() || nums[start] != target) {
            return {-1, -1};
        }

        // 如果 start 存在，那么 end 必定存在
        int end = lower_bound(nums, target + 1) - 1;
        return {start, end};
    }
};

复杂度分析

时间复杂度：$O(logn)$。

空间复杂度：$O(1)$。

方法二：使用库函数

对于上述手写二分查找的函数，C++ 标准库中有对应的函数 $\text{lower\_bound}$ 实现相同的功能。不论是库函数，还是手写二分查找都需要掌握。

代码

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

        int end = lower_bound(nums.begin(), nums.end(), target + 1) - nums.begin() - 1;
        return {start, end};
    }
};

知识回顾

二分查找的三种写法与三个问题

二分查找有三种写法：闭区间、左闭右开和开区间写法，无论是哪种写法，始终都要关注三个问题：

• 何时退出循环，二分查找据此有了三种写法
• 指针如何移动
• 最后返回什么

关于以上三种写法与三个问题，可以参考 【面试经典 150 | 二分查找】搜索插入位置。

常用的二分库函数

$\text{lower\_bound(beg, end, val)}$
返回一个迭代器，表示 第一个不小于（大于等于） val 的元素，如果不存在这样的元素则返回 end 迭代器。
$\text{upper\_bound(beg, end, val)}$
返回一个迭代器，表示 第一个大于 val 的元素，如果不存在这样的元素则返回 end 迭代器。
$\text{equal\_range(beg, end, val)}$
返回一个 pair，其 first 成员是 $\text{lower\_bound}$ 返回的迭代器，second 成员是 $\text{upper\_bound}$ 返回的迭代器。
$\text{binary\_search(beg, end, val)}$ 返回一个 bool 值，指出序列中是否包含等于 val 的值。

以上每一个函数都提供一个第二版本，这个版本可以自定义比较操作。

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。