基础

class Solution {
    public int search(int[] nums, int target) {
        return binarySearch(nums, target);
    }

    private int binarySearch(int[] nums, int target) {
        int l = 0, r = nums.length - 1, m;
        while (l <= r) {
            m = (l + r) >>> 1;
            if (nums[m] == target) return m;
            else if (nums[m] < target) l = m + 1;
            else r = m - 1;
        }
        return -1;
    }
}

解决整数溢出

m = l + (r - l) / 2; // avoid overflow

m = (l + r) >>> 1; // avoid overflow

左边界问题

找不小于 target 的最小（最左边）的数

int left_bound(int[]nums,int target){
    int left = 0,right = nums.length-1,mid=0;
    while(left<=right){
        mid = left +(right-left)/2;
        if (nums[mid] >= target){
            right = mid-1;
        } else {
            left = mid+1;
        }
    }
    // 如果搜索的数字比所有的都大，最终right位置在最后一个元素，left = right+1
    //             比所有的都小，最终left 在0 。所以如果left>=nums.length || nums[left]!=target则未找到
    if(left>=nums.length || nums[left]!=target){
        return -1;
    }
    return left;
    
}

• 另一种写法（隐藏）

右边界问题

找不大于 target 的最大（最右边）的数

int right_bound(int[] nums,int target){
    int left = 0,right = nums.length-1,mid = 0;
    while(left<=right){
        mid = left +(right-left)/2;
        if (nums[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    if (right < 0 || nums[right] != target) {
        return -1;
    }
    return right;
}

• 另一种写法（隐藏）

<aside> 👨‍💻 例题：69. x 的平方根 74. 搜索二维矩阵 300. 最长递增子序列

</aside>