二分法的进阶

这是我参与8月更文挑战的第2天，活动详情查看：8月更文挑战

这篇文章是之前更文挑战第一天二分法入门 的续集。
很多时候，我们遇到的实际场景不仅仅是找到对应的数这么简单，当数组中可能存在相同的数的时候，可能会有多个目标值存在于数组中，实际场景可能要求我们求出目标值范围的左边界或者右边界。下文中我们依然假设数组是从小到大排序的。

如果使用找到一个目标值后开始向左或者向右线性遍历的话，就无法保证二分法对数级别的时间复杂度了。所以在找到目标值时不应该返回，而是应该进一步缩小查找范围。

查找左边界

当找到目标值时，不应该立刻返回，而是应该进一步缩小右边界

下面给出一个左闭右开情况下的例子：

if(target==nums[mid])
{
right=mid;
}
复制代码

既然找到目标值也不会直接返回，那么必然是在while循环结束的时候才会给出返回值，此时left==right

返回值

当left==right-1，也就是左右边界之间只有一个元素的时候，mid必定比right小。假设我们在数组中能找到目标值的情况下，左闭右开情况下，right应该就相当于右数最后一个目标值的下标，此时left向right靠拢，所以返回left或right都可以。

但是我们还要考虑数组中不存在目标值的情况。

由于初始left=0，right=length（左闭右开的情况下）,前文说过mid必定小于right，考虑极端情况（left一直等于mid+1，或者right一直等于mid，参考之前的公式），最终左边界的取值就是[0,length]。

if(nums[mid]<target)
    {
        left=mid+1;
    }
else if(nums[mid]>target)
    {
        right=mid;
    }
复制代码

对于一个左边界index，index==0既可以说明左数第一个就是他的左边界，也可以说明完全没有找到对应的数。

但是如果index==length,就只有一种情况，那就是没有找到对应的数。换句话说，左边界的值其实就代表”数组中有多少个值比我更小“。

下面给出对返回值的判断代码示例。

//left或者right都可以
if(left==nums.length) 
{
    return -1;
}
else if(left==0) 
{
    if(target==nums[left])
    {return left;}
    else
    {return -1;}
}
else
{
    return left;
}
复制代码

还可以再精简一下，合并相同的逻辑

if(left==nums.length) 
{
    return -1;
}
return target==nums[left]?left:-1;
复制代码

查找右边界

同理，我们找到目标值时不可以立刻返回，而是增大左边界继续查找。

if(target==nums[mid])
{
left=mid+1;
}
复制代码

返回值

查找右边界的返回值是要注意的，假设我们能在数组中找到该目标值，在左闭右开的情况下，left一般来说等于左数最后一个目标值下标+1，所以返回left-1或者right-1都可以。

判断边界的情况反过来即可

if(left==0) 
{
    return -1;
}
return target==nums[left-1]?left-1:-1;
复制代码