二分查找

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

二分查找是否存在target模板

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

public boolean binarySearch(int[] arr,int target){
    int left=0,right=arr.length-1;
    while(left<=right){//终止条件是left=right+1
        int mid=(left+right)>>>1;//使用无符号位移防止溢出
        if(arr[mid]<target){
            left=mid+1;
        }else if(arr[mid]>target){
            right=mid-1;
        }else{
            return true;
        }
    }
    return false;
}

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

二分查找最左侧的target模板

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

public int binarySearch(int[] arr,int target){
    int left=0,right=arr.length;
    while(left<right){//终止条件是left=right
        int mid=(left+right)>>>1;
        if(arr[mid]>=target){
            right=mid;
        }else{
            left=mid+1;
        }
    }
    return left;
}

二分边界查找相关练习

• LeetCode：1011. 在 D 天内送达包裹的能力（capacity-to-ship-packages-within-d-days）

二分查找

原文：https://www.cnblogs.com/takagi/p/14703882.html