二分搜索

在没有重复值的排序数组中搜索，或者不关心是否有重复值

/*
* @nums：排序数组
* @target：要搜索的值
* @return：-1，没有target值;!=-1,target在nums中的索引
*/
public int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; 

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

在有重复值的排序数组中搜索左侧边界

/*
* @nums：排序数组
* @target：要搜索的值
* @return：-1，没有target值;!=-1,target在nums中第一次出现时的索引
*/
public int leftBound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; 

    while (left < right) { 
        int mid = left + (right- left) / 2;
        if (nums[mid] == target) {
            right = mid; // 找到 target 时不要立即返回，而是缩小「搜索区间」的上界 right，在区间 [left, mid) 中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; 
        }
    }
    // while循环结束后，left保存的是k第一次出现时的索引 left的取值范围是[0, array.length]
    
    // target 比所有数都大
    if (left == nums.length) return -1;
    // 处理left = 0的情况。
    return nums[left] == target ? left : -1;
}

在有重复值的排序数组中搜索右侧边界

/*
* @nums：排序数组
* @target：要搜索的值
* @return：-1，没有target值;!=-1,target在nums中第一次出现时的索引
*/
public int rightBound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;

    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 当 nums[mid] == target 时，不要立即返回，而是增大「搜索区间」的下界 left，使得区间不断向右收缩，达到锁定右侧边界的目的。
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    // while循环结束后，left = right,left 的取值范围是 [0, nums.length]
    
    // target 比所有数都小
    if (left == 0) return -1;
    return nums[left-1] == target ? (left-1) : -1;
}

https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247484507&idx=1&sn=36b8808fb8fac0e1906493347d3c96e6&source=41#wechat_redirect