算法--二分查找

二分查找：

• 前提：数组有序
• 时间复杂度：O(log2 n)

public int binarySearch(int[] nums, int target) {
    int l=0,r=nums.length-1;//初始l指向第一个元素，r指向最后一个元素
    while(l<=r){//l和r指向的元素都作为比较元素，l=r时，需进行比较
        int m=(l+r)>>>1;//防止溢出
        if (target<nums[m]){//目标值比中间值小，r指针往左缩小范围
            r=m-1;
        }else if (nums[m]<target){//目标值比中间值大，l指针往右缩小范围
            l=m+1;
        }else {//目标值与中间值相等，则找到
            return m;
        }
    }
    return -1;//如果为return l;当targer在数组中不存在时返回在数组中的插入位置
}

lower_bound：返回第一个大于等于target的元素下标（相当于targer在左边的插入位置）

public int lowerBound(int[] nums, int target) {
    int l=0,r=nums.length-1;
    while (l<=r){
        int m=(l+r)>>>1;
        if (target<=nums[m]){//目标值比中间值小，r指针往左缩小范围，目标值与中间值相等，r指针继续往左缩小范围，这样就能找到目标值最左边的元素
            r=m-1;
        }else {
            l=m+1;
        }
    }
    return l;
}

upper_bound：返回第一个大于target的元素下标（相当于targer在右边的插入位置）

public int upperBound(int[] nums, int target) {
    int l=0,r=nums.length-1;
    while (l<=r){
        int m=(l+r)>>>1;
        if (target>=nums[m]){//目标值比中间值大，l指针往右缩小范围，目标值与中间值相等，l指针继续往右缩小范围，这样就能找到目标值最右边的元素
            l=m+1;
        }else {
            r=m-1;
        }
    }
    return l;
}

lower_bound、upper_bound当targer在数组中不存在时返回targer的插入位置。
二分查找左指针最终指向的位置为targer的插入位置。

• 本文作者： zzr
• 本文链接： http://zzruei.github.io/2023/092d8a8292.html
• 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！