二分查找笔记

对于长度为N的数组

寻找某个值是否存在

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

寻找左侧边界

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

寻找右侧边界

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