二分查找细节

1.while(l<r) [l,r) 与while(l <= r) [l,r]
分别对应l = mid + 1, r = mid 和 l = mid + 1, r = mid -1
2.三个if()写清楚条件，而不是用else省略第三种情况的条件。
3.搜索插入点时，while循环执行完时，l < r,left == right即为插入点,l <= r,left仍为插入点，r = l – 1。实际上在最后一次nums[mid] == target时即可返回。
3.如果要找左右边界，需要修改nums[mid] == target的内容，不是直接返回，找左边界时，l < r，r = mid,l < =r,r = mid – 1,找右边界时，l < r, l = mid + 1, l <= r, l = mid + 1。需要在while循环执行完才能拿到结果，结果仍为插入点，如果需要专门对未找到返回-1，还需额外判断。
4.mid = left + (right – left) / 2 而不是 mid = (right + left) / 2，防止溢出。

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}