二分查找(搜索区间为左闭右开)

• 二分查找(搜索区间为左闭右开)
• • 0. 参考链接
  • 1. 思考
  • 2. lower_bound的相同效果实现思路
  • • 2.1 循环条件
    • 2.2 边界调整
    • 2.3 返回结果
  • 3. upper_bound的相同效果实现思路
  • • 3.1 循环条件
    • 3.2 边界调整
    • 3.3 返回结果
  • 4. 其他
  • 5. 例

二分查找有几种写法？它们的区别是什么？ - Jason Li的回答

我认为二分查找是容易出bug的算法，因为它的整体的思路很简单，但它关于细节的问题太多。

比较麻烦的问题有以下几个

假设l是搜索区间左边界，r是搜索区间右边界，m是向下取整中位点, A为有序表

• 循环条件： l < r 还是 l <= r ？

• 边界调整： l = m 还是 l = m + 1； r = m 还是 r = m - 1 ？

• 返回结果： return 的结果是{l，l+1，r，r+1} ？

以上问题可以通过取左闭右开的搜索区间来尝试解决，最终结论如下

• 循环条件： l < r （搜索区间不为空）
• 边界调整： l = m + 1， r = m
• 返回结果： return l 或 return r 均可

个人感性认识上

正是因为二分除法中中位数有两种取法的问题，左闭右开直接偏向选择了向下取整的中位数

m = (l + r) / 2 而不是 m = (l + r + 2) / 2，来减少讨论。

C++STL库实现的二分查找函数，提供的参数也是相同的思路

lower_bound(first,last,value)：从下标[first, last)内，二分查找第一个大于或等于value的数字

upper_bound(first,last,value)：从下标[first, last)内，二分查找第一个大于value的数字

// 求 第一个 x >= v
while (l < r) { 
    m = l + ((r - l) >> 1);	// 防溢
    if (A[m] < v) l = m + 1;
    else r = m;
}
return l; // 或 return r;

在查找过程中循环继续的条件

• [l,r)不为空，需要继续搜索
• 此时[l₀,l)所有元素(若存在)都
• 此时[r,r₀)所有元素(若存在)都>=v

• A[m]0,l)区间内 应调整 m < l，则 l = m + 1

• A[m]>=v，那么m在[r,r₀)区间内 应调整 m >= r，则 r = m

最终循环结束时

• [l,r)为空, l = r

• [l₀,l)所有元素(若存在)都

• [r,r₀)所有元素(若存在)都>=v，r为所求下界

// 求 第一个 x > v
while (l < r) { 
    m = l + ((r - l) >> 1);
    if (A[m] <= v) l = m + 1;	// 差别在此，A[m] == v 的归属
    else r = m;
}
return l; // 或 return r;

在查找过程中循环继续的条件

• [l,r)不为空，需要继续搜索
• 此时[l₀,l)所有元素(若存在)都<=v
• 此时[r,r₀)所有元素(若存在)都>v

• A[m]<=v，那么m在[l₀,l)区间内 应调整 m < l，则 l = m + 1

• A[m]>v，那么m在[r,r₀)区间内 应调整 m >= r，则 r = m

最终循环结束时

• [l,r)为空, l = r

• [l₀,l)所有元素(若存在)都<=v，

• [r,r₀)所有元素(若存在)都>v，r为所求下界

可以用lower_bound和upper_bound解决常用二分查找问题如下

• 小于v的上界 lower_bound(l,r,v) - 1
• 小于等于v的上界 upper_bound(l,r,v) - 1
• 大于等于v的下界 lower_bound(l,r,v)
• 大于v的下界 upper_bound(l,r,v)

中间两个较为常用

LeetCode 35.搜索插入位置

int searchInsert(int* nums, int numsSize, int target)
{
    int l, r;
    l = 0, r = numsSize;
    while (l < r) { 
        int m = l + ((r - l) >> 1);
        if (nums[m] < target) l = m + 1;
        else r = m;
    }
    return l;
}

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

int* searchRange(int* nums, int numsSize, int target, int* returnSize)
{
    int l = 0, r = numsSize, m;
    int* ret = malloc(sizeof(int) * 2);
    *returnSize = 2;
    ret[0] = ret[1] = -1;

    if (numsSize == 0) return ret;

    while(l < r) {
        m = l + ((r - l) >> 1);
        if (nums[m] < target) l = m + 1;
        else r = m;
    }
    if (r != numsSize && nums[l] == target) ret[0] = l;

    l = 0, r = numsSize;
    while (l < r) {
        m = l + ((r - l) >> 1);
        if (nums[m] <= target) l = m + 1;
        else r = m;
    }  
    if (l != 0 && nums[l - 1] == target) ret[1] = l - 1;

    return ret;
}