二分查找

二分查找可以分为查找一个目标值target是否存在和查找一个连续递增的数组中存在着多个相同target的最左边界或者最右边界。

二分查找是否存在target模板

下面这个模板中的输入数组是一个递增数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
boolean binarySearch(int[] arr,int tar){
    int l=0,r=arr.length-1;
    while(l<=r){//终止条件是left=right+1
        int mid=l+r>>>1;//使用无符号位移防止溢出
        if(arr[mid]<tar){
            l=mid+1;
        }else if(arr[mid]>tar){
            r=mid-1;
        }else{
            return true;
        }
    }
    return false;
}

若果索引是负数的为了防止溢出mid可以使用mid=left+(right-left)/2。

二分查找最左侧的target模板

如果一个递增数组中存在着连续的target而我们需要查找这个数组中最左侧的target的下标：

1
2
3
4
5
6
7
8
9
10
11
12
int ls(int[] nums,int tar){
    int l=0,r=nums.length-1;
    while(l<r){
        int mid=l+r>>>1;//向下取整（最左向下，最右向上）
        if(nums[mid]<tar){
            l=mid+1;
        }else{
            r=mid;
        }
    }
    return l;
}

二分查找最右侧target模板

如果一个递增数组中存在着连续的target而我们需要查找这个数组中最右的target的下标：

1
2
3
4
5
6
7
8
9
10
11
12
int rs(int[] nums,int tar){
    int l=0,r=nums.length-1;
    while(l<r){
        int mid=l+r+1>>>1;//向上取整（最左向下，最右向上）
        if(nums[mid]>tar){
            r=mid-1;
        }else{
            l=mid;
        }
    }
    return r;
}

二分边界查找相关练习