当前位置：首页 > article >正文

【面试经典 150 | 二分查找】搜索插入位置

article 2024/9/25 9:33:27

文章目录

写在前面
Tag
题目来源
题目解读
解题思路
- 方法一：二分查找
- - 闭区间
  - 左闭右开区间
  - 开区间
  - 总结
知识总结
写在最后

写在前面

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

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

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

Tag

【二分查找】【数组】

题目来源

35. 搜索插入位置

题目解读

其实就是找出数组中大于等于 target 的最小值所在的位置。

解题思路

在数组中找到第一个大于或者等于 target 值的所在位置，数据量不大，约为 $O(10^4)$ ，可以一次遍历查找，也开始使用二分查找来解决。题目要求使用时间复杂度为 $O (l o g n)$ 的算法，那就只能使用二分法来解答了。

方法一：二分查找

二分查找是一种高效的搜索算法，在有序数组的指定区间内根据要求搜索元素，根据当前区间的中点的搜索情况缩短区间，每次搜索都会缩短一半的区间，时间复杂度为 $O (l o g n)$ ， $n$ 为有序数组的长度。

二分查找根据区间的开闭分为以下三种情况：

闭区间；
左闭右开区间；
开区间。

二分查找的区间无论是哪种闭合形式，要关注的问题始终是三个：

一是何时退出循环；
二是表示左、右区间的左、右指针如何移动；
三是返回什么。

以下将针对三种二分法的三个问题分别进行分析。

闭区间

闭区间表示搜索的区间是闭合的，初始的闭合区间为 [0, n-1]，即指针指向 l = 0, r = n-1。

何时退出循环？

当区间为空的时候退出 while 循环，何时区间为空？

当 l > r 时，指针 l 位于指针 r 右侧已经构不成区间了，退出 while 循环。

因此，此时的 while 循环条件为 l <= r。

左、右指针如何移动？

在闭区间情况下，如果 nums[mid] < target，说明 >= target 的值在右侧区间，于是只需要更新左指针 l = mid + 1；否则（nums[mid] >= target）说明 mid 及其之后的位置都是确定大于 target 的，这时候需要更新右指针 r = mid - 1 来判断左区间内的数。

返回什么？

退出循环后，r 指向的位置为 l 指向位置左侧的第一个位置，最后返回 l 或者 r + 1。

实现代码

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l <= r) {        // 区间为空退出循环
            int mid = l + ((r - l) >> 1);
            if (nums[mid] < target) {
                l = mid + 1;
            }
            else {
                r = mid - 1;
            }
        }
        return l; // 等价于 return r+1
    }
};

左闭右开区间

左闭右开区间表示搜索的区间是左闭右开的，初始的指针指向为 l = 0, r = n。

何时退出循环？

当区间为空的时候退出 while，何时区间为空？

因为 r 指针是取不到的，所以当 l = r 时，区间为空（因为实际的区间左端点为 l，右端点为 r，构不成区间），退出 while 循环。

此时的 while 循环条件为 l < r。

左、右指针如何移动？

在左闭右开区间情况下，如果 nums[mid] < target，说明 >= target 的值在右侧区间，于是只需要更新左指针 l = mid + 1；否则（nums[mid] >= target）说明 mid 及其之后的位置都是确定大于 target 的，这时候需要更新右指针 r = mid 来判断左区间即 [l, mid-1] 中的数。

返回什么？

退出循环后，r 和 l 指向的是同一个位置，最后返回 l 或者 r。

实现代码

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n;
        while (l < r) {        // 区间为空退出循环
            int mid = l + ((r - l) >> 1);
            if (nums[mid] < target) {
                l = mid + 1;
            }
            else {
                r = mid;
            }
        }
        return l; // 等价于 return r
    }
};

开区间

开区间表示搜索的区间两边都是开的，初始的指针指向为 l = -1, r = n。

何时退出循环？

当区间为空的时候退出 while，何时区间为空？

因为 l 和 r 指针指向的值是取不到的，所以当 l + 1 = r 时，(l, r) 表示的区间为空，退出 while 循环。

此时的 while 循环条件为 l + 1 < r。

左、右指针如何移动？

在开区间情况下，如果 nums[mid] < target，说明 >= target 的值在右侧区间，于是只需要更新左指针 l = mid（因为左区间是开的，实际的区间是 mid + 1）；否则（nums[mid] >= target）说明 mid 及其之后的位置都是确定大于 target 的，这时候需要更新右指针 r = mid 来判断左区间即 [l, mid - 1] 中的数。

返回什么？

退出循环后，l 指向的位置位于 r 指向位置的左侧，最后返回 r 或者 l+1。

总结

无论是哪种区间闭合形式，关注的始终是：何时退出while循环、左右指针如何更新以及最后返回什么这三个问题。

需要注意的移动指针一定要保证原来区间的闭合与否：原来区间是闭合的，更新后的指针指向的依旧是闭合的区间；原来区间是开的，更新后的指针指向的依旧是开的区间。

以上三种形式，可以挑选一种自己熟悉的形式记忆，并记住这是解决在有序数组中查找大于等于指定值的代码。

知识总结

在有序数组中查找大于等于指定值的最小位置的二分查找方法是十分经典，该方法已经被封装成了一个函数 lower_bound()，该方法之所以是经典是因为其他类型的查找都可以通过它来完成：

在有序数组中查找大于等于指定值的最小位置，这就不赘述了；
在有序数组中查找大于指定值 x 的最小位置，本题及以下等价转换仅限于整数数组。此时可以等价转化为 “在有序数组中查找大于等于指定值 x+1 的最小位置”；
在有序数组中查找小于指定值 x 的最大位置，可以等价转化为 “在有序数组中查找大于等于指定值 x 的最小位置” 减 1；
在有序数组中查找小于等于指定值 x 的最大位置，可以等价转化为 “在有序数组中查找大于等于指定值 x+1 的最小位置” 减 1。