二分法

二分法作为一种常见的查找算法，其实不单单可以只寻找某一个数。

最基本的二分查找

搜索一个数，如果存在，返回其索引，否则返回 -1。

// 搜索一个数
int binarySearch(vector<int>& nums, int target) 
{
    int left = 0;
    int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
    while (left < right) 
    {   // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
        int mid = left + ((right - left) >> 1);
        if (nums[mid] > target) 
            right = mid;    // target 在左区间，在[left, mid)中
        else if (nums[mid] < target)
            left = mid + 1; // target 在右区间，在[mid + 1, right)中
        else                // nums[mid] == target
            return mid;     // 数组中找到目标值，直接返回下标
    }
    
    return -1;              // 未找到目标值
}

搜索左侧边界

如上图所示，查找数组中最左侧大于或等于3的数也可以使用二分法。首先对整个数组二分，看中间的数是否满足大于或等于3，若满足继续在左侧二分，否则在右半侧二分，一直到结束，得到的所有满足条件的最小下标就是求得的结果。

这个问题与普通二分法查找的区别在于：二分法是使用二分找个一个满足条件的数之后就结果查找，但是这里需要一直二分到最后，然后在所有满足条件的数中比较。

搜索左侧边界的二分搜索算法的具体代码实现如下：

// 搜索左侧边界
int left_bound(vector<int>& nums, int target) 
{
    if (nums.size() == 0) 
        return -1;
    int left = 0, right = nums.size();
    
    while (left < right) 
    {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target) 
            right = mid;    // 当找到 target 时，收缩右侧边界
        else if (nums[mid] < target) 
            left = mid + 1;
        else if (nums[mid] > target) 
            right = mid;

    }
    if(left == nums.size())     // 没有搜索到
        return -1;
    return nums[left] == target ? left : -1;    // nums[left] != target说明没有搜索到，返回-1
}

注意在搜索左侧边界的时候并不是一旦发现nums[mid] == target就直接返回，因为要寻找最左侧满足条件的下标。

简化后的代码如下：

// 优化版搜索左侧边界
int left_bound(vector<int>& nums, int target) 
{
    if (nums.size() == 0) 
        return -1;
    int left = 0, right = nums.size();
    
    while (left < right) 
    {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] >= target) 
            right = mid;  
        else
            left = mid + 1;
    }
    if(left == nums.size())     // 没有搜索到
        return -1;
    return nums[left] == target ? left : -1;    // nums[left] != target说明没有搜索到，返回-1
}

搜索右侧边界

搜索右侧边界其实和搜索左侧边界同理，不同的地方在于，搜索左侧边界时出现nums[mid] == target时right需要向左收缩，而在搜索右侧边界的时候出现nums[mid] == target时是left需要向右收缩。

代码如下：

// 搜索右侧边界
int right_bound(vector<int>& nums, int target) 
{
    int left = 0, right = nums.size();

    while (left < right) 
    {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target)
            left = mid + 1;     
        else if (nums[mid] < target)
            left = mid + 1;
        else if (nums[mid] > target)
            right = mid;
    }
    if(left - 1 < 0)    // 没有搜索到
        return -1;
    return nums[left - 1] == target ? left - 1 : -1; // nums[left - 1] != target说明没有搜索到，返回-1
}
}

将nums[mid] == target和nums[mid] < target的情况合并之后的简化版为：

// 搜索右侧边界
int right_bound(vector<int>& nums, int target) 
{
    int left = 0, right = nums.size();

    while (left < right) 
    {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target)
            left = mid + 1;     
        else
            right = mid;
    }
    if(left - 1 < 0)    // 没有搜索到
        return -1;
    return nums[left - 1] == target ? left - 1 : -1; // nums[left - 1] != target说明没有搜索到，返回-1
}

attention

不管是搜索单个值还是左右侧边界，此模板中left和right收缩的模式是一样的，即left向右收缩时总是left = mid + 1,而right收缩时总是right = mid。为什么 left 的更新必须是 left = mid + 1，当然是为了把 nums[mid] 排除出搜索区间。记住这一点便很容易记下三种不同的模板。

另外，搜索左右侧边界时的返回也不一样，搜索左侧边界的时候返回是left，而在搜索右侧边界的时候返回是left - 1，因为我们对 left 的更新必须是 left = mid + 1，就是说 while 循环结束时，nums[left] 一定不等于 target 了，而 nums[left-1] 可能是 target。