算法与数据结构——二分查找插入点，查找边界

创作时间:

作者:

@小白创作中心

算法与数据结构——二分查找插入点，查找边界

引用

来源

https://www.cnblogs.com/1873cy/p/18409659

二分查找是一种高效的搜索算法，广泛应用于有序数组的查找场景。本文将深入探讨二分查找在不同场景下的应用，包括无重复元素和有重复元素情况下的插入点查找，以及查找左边界和右边界的方法。通过具体的代码示例和图解，帮助读者全面理解二分查找的变种问题。

二分查找插入点

二分查找不仅可用于搜索目标元素，还可以解决许多变种问题，比如搜索目标元素的插入位置。

无重复元素情况

Question
给定一个长度为n的有序数组
nums
和一个元素
target
，数组不存在重复元素。现将
target
插入数组
nums
中，并保持其有序性。若数组中已存在元素
target
，则插入到其左方。请返回插入后
target
在数组中的索引。

问题一：当数组中包含
target
时，插入点的索引是否就是该元素的索引？
题目要求将
target
插入到相等元素的左边，这意味着插入的
target
替换了原来
target
的位置。也就是说，当数组包含
target
时，插入点的索引就是该
target
的索引。

问题二：当数组中不存在
target
时，插入点是哪个元素的索引？
进一步思考二分查找过程（m为中点索引）：当
nums[m] < target
时，这意味着指针i在向大于等于
target
的元素靠近。同理，指针j始终在向小于等于
target
的元素靠近。
因此二分结束时一定有：i指向首个大于
target
的元素，j指向首个小于
target
的元素。易得当数组不包含
target
时，插入索引为i。

代码示例如下：

/*二分查找插入点（无重复元素）*/
int binarySearchInsertionSimple(vector<int> &nums, int target){
    int i = 0, j = nums.size() - 1;
    while (i <= j){
        int m = i + (j - i) / 2;
        if (nums[m] < target)
            i = m + 1;
        else if (nums[m] > target)
            j = m - 1;
        else
            return m;  // 找到target 返回插入点 m
    }
    return i;			// 未找到 target，返回插入点 i
}

存在重复元素的情况

假设数组中存在多个
target
，则普通二分查找只能返回其中一个
target
的索引，而无法确定该元素的左边和右边还有多少个
target
。
题目要求将目标元素插入到最左边，所以我们需要查找数组中最左一个
target
的索引。
实现步骤：
2. 执行二分查找，得到任意一个
target
索引，记为k。
4. 从索引k开始，向左进行线性遍历，当找到最左边的
target
时返回。
此方法虽然可用，但其包含线性查找，因此时间复杂度为O(n)。当数组中存在很多重复的
target
时，该方法效率很低。
现考虑拓展二分查找代码。如图所示，整体流程保持不变，每轮现计算中点索引m，再判断
target
和
nums[m]
的大小关系，分以下几种情况：

当
nums[m] < target
或
nums[m] > target
时，说明还没有找到
target
，因此采用普通二分查找的缩小区间操作，从而使指针i和j向
target
靠近。
当
nums[m] == target
时，说明小于
target
的元素在区间[i,m-1]中，因此采用j = m-1来缩小区间，从而使指针j向小于
target
的元素靠近。
循环完成后，i指向最左边的
target
，j指向首个小于
target
的元素，因此索引i就是插入点。

观察以下代码，其中判断分支
nums[m] > target
和
nums[m] == target
的操作相同，因此两者可以合并。即便如此，我们仍然可以将判断条件保持展开，因为逻辑更加清晰、可读性更好。

/*二分查找插入点（存在重复元素）*/
int binarySearchInsertion(vector<int> &nums, int target){
    int i = 0, j = nums.size() - 1;
    while (i <= j){
        int m = i + (j - 1) / 2;
        if (nums[m] < target)
            i = m + 1;		// target 在区间 [m+1, j] 中
        else if (nums[m] > target)
            j = m - 1;		// target 在区间 [i, m-1] 中
        else
            j = m - 1;		// 首个小于 target 的元素在区间 [i, m-1] 中
    }
    // 返回插入点
    return i;
}

总的看来，二分查找无非就是给指针i和j分别设定搜索目标，目标可能是一个具体元素（例如
target
），也可能是一个元素范围（如小于
target
的元素）。
在不断的循环二分中，指针i和j都逐渐逼近预先设定的目标。

二分查找边界

查找左边界

Question
给定一个长度为n的有序数组
nums
，其中可能包含重复元素。请返回数组中最左一个元素
target
的索引。若数组中不包含该元素，则返回-1。

在二分查找插入点的方法中，搜索完成后i指向最左一个
target
，因此查找插入点本质上是在查找最左一个
target
的索引。
考虑通过查找插入点的函数实现查找左边界。注意，数组中可能不包含
target
，这种情况可能导致以下两种结果：

插入点的索引i越界
元素
nums[i]
与
target
不相等
当遇到以上两种情况时，直接返回-1即可。

/*二分查找最左一个target*/
int binarySearchLeftEdge(vector<int> &nums, int target){
    // 等价于查找 target 的插入点
    int i = binarySearchInsertion(nums, target);
    // 未找到 target ，返回 -1
    if (i == nums.size() || nums[i] != target) {
        return -1;
    }
    // 找到 target ，返回索引 i
    return i;
}

查找右边界

最直接的方式是修改二分查找代码，替换在
nums[m] == target
情况下的指针收缩策略。下面介绍两种更加取巧的方法。

复用查找左边界

实际上，我们可以利用查找最左元素的函数来查找最右元素，具体方法为：将查找最右一个
target
转化为查找最左一个
target + 1
。
如图所示，查找完成后，指针i指向最左一个
target + 1
（如果存在），而j指向最右一个
target
，因此返回j即可。

/*二分查找最右一个 target*/
int binarySearchRightEdge(vector<int> &nums, int target){
    // 转化为查找最左一个 target + 1
    int i = binarySearchInsertion(nums, target + 1);
    // j 指向最右一个 target ，i 指向首个大于 target 的元素
    int j = i - 1;
    // 未找到 target ，返回 -1
    if (j == -1 || nums[j] != target) {
        return -1;
    }
    // 找到 target ，返回索引 j
    return j;
}