二分查找(The search range is left closed and right open)

0. 参考链接

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

1. 思考

I think binary search is easy to figure outbug的算法,Because its overall idea is very simple,But it's too much about the details.

The more troublesome problems are as follows

假设lis the left boundary of the search interval,ris the right boundary of the search interval,mis the rounded down median, A为有序表

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

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

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

The above problems can be solved by taking a search interval that is closed on the left and open on the right,最终结论如下

• 循环条件： l < r （The search range is not empty）
• 边界调整： l = m + 1, r = m
• 返回结果： return l 或 return r 均可

personal perception

It is because of the binary divisionThere are two ways to take the median的问题,Left closed right open directly biased selectionThe median rounded down

m = (l + r) / 2 而不是 m = (l + r + 2) / 2,to reduce discussion.

C++STLThe binary search function implemented by the library,The parameters provided are the same idea

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

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

2. lower_boundThe same effect achieves the idea

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

2.1 循环条件

The condition under which the loop continues during the search

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

2.2 边界调整

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

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

2.3 返回结果

最终循环结束时

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

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

• [r,r₀)所有元素(若存在)都>=v,rFor the desired lower bound

3. upper_boundThe same effect achieves the idea

// 求 第一个 x > v
while (l < r) {
     
    m = l + ((r - l) >> 1);
    if (A[m] <= v) l = m + 1;	// The difference is here,A[m] == v 的归属
    else r = m;
}
return l; // 或 return r;

3.1 循环条件

The condition under which the loop continues during the search

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

3.2 边界调整

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

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

3.3 返回结果

最终循环结束时

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

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

• [r,r₀)所有元素(若存在)都>v,rFor the desired lower bound

4. 其他

可以用lower_bound和upper_boundSolve the common binary search problem as follows

• 小于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)

The middle two are more common

5. 例

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;
}