【算法】【二分】二分查找总结

找精确值模板

int l = 0, r = n - 1;
while(l <= r)
{
    int mid = l + r >> 1;
    if(arr[mid] == target) return mid;
    else if(arr[mid] > target) r = mid - 1;
    else l = mid + 1;
}
return -1;

查找大于等于/大于 target 的第一个元素

int l = 0, r = n - 1;
//设mid = i, 
//如果nums[mid] > target， 那么r = l = i; 跳出循环；
//如果nums[mid] < target,  那么l = r = i + 1; 跳出循环；
//不存在死循环
while(l < r)
{
    //找大于等于target的第一个元素
    int mid = (l + r)  >> 1;
    if(nums[mid] >= target) r = mid; //如果是大于 改成 >
    //因为要找比nums[mid]大的元素，所以nums[mid]肯定不是答案 已经判断过了； l = mid + 1;
    else l = mid + 1; 
}
return l;

查找小于等于/小于 target 的最后一个元素

int l = 0, r = n - 1;
while(l < r)
{
    //找小于等于target的最后一个元素
    int mid = (l + r + 1)  >> 1;
    //考虑只剩下nums[i]和nums[i + 1]，如果不加1，那么mid = i;
    //如果nums[mid] < target, 更新后 l = mid, r = mid + 1;会产生死循环；
    //加上1以后，mid = i + 1;
    //如果nums[mid] < target, l = r = mid + 1; 跳出循环；
    //如果nums[mid] > target, l = r = i; 跳出循环； 
    if(nums[mid] <= target) l = mid; //如果是小于 改成 <
    else r = mid - 1;
}
return l;

说明

循环的判断条件l <= r?

• 区间变换思路是不断的舍去不可能是解的区间，最后只剩下一个数就是我们的解。而第一种情况就算最后只剩一个数也有可能不是解，所以需要使用小于等于。