如何使用二分查找定位数组中不存在元素的下界索引

问题场景 #

当目标元素未出现在升序数组中时，可通过二分查找算法获取该元素的下界（lower bound）索引。

输入输出规则 #

• 输入顺序：依次输入数组长度、待查找目标元素值
• 示例输入：5 4
• 对应测试数组元素：1 2 3 7 8
• 示例输出：2，即目标元素对应的下界数组索引

参考实现代码 #

注意：初始化时左边界low设为0，右边界high设为数组长度减1，循环结束后即可得到目标索引值

while(low <= high){
    int mid = (high + low)/2;

    if(a[mid] < s){
        low = mid + 1;
    }  
    else if(a[mid] >= s){
        high = mid - 1;
    }
}

代码逻辑：每次取区间中间位置元素和目标值比较，如果中间元素小于目标值，说明目标位置在右半区间，将左边界移动到中间位置右侧；如果中间元素大于等于目标值，说明目标位置在左半区间，将右边界移动到中间位置左侧，区间收缩完成后即可得到结果。

测试用例参考 #

• 测试用例1：
  
• 测试用例2：
  

内容的提问来源于stack exchange，提问作者ProgrammerSK