二分搜索中mid的确定

Question

我的环路卡在这里，所以我在一些情况下得到了TLE。在意识到这个问题（反复选择低）后，我将mid改为low+(high-low+1)/2，通过了这个更改，整个测试用例都通过了。（代码1）

我也做了一个类似的问题，我使用了(low+high)/2，它也通过了所有的测试用例。

我的问题是我们如何决定如何选择MID？

public static boolean subarray(int mid,long x,long[] sum,int[] a){
    int n=a.length;
    for(int i=0;i<n-mid+1;i++){
    if(sum[mid+i-1]-sum[i]+a[i]>x){
        return false;
    }

    }
    return true;

}

public static void binarysearch(long[] sum,int [] a,long x){
    int low=1;
    int high=a.length;

    while(low!=high){
        int mid=low+ (high-low+1)/2; //passed
        //int mid=(low+high)/2;    did n't PASS

        if(!subarray(mid,x,sum,a)){//if some greater then x
            high=mid-1;              
        }
        else{
             //if some less then x okay but can go for more
            low=mid;

        }
    }
    System.out.println(low);

}

    public static long binarysearch(long[] a,long x,long[] L,long[] R){
    //find first index >= x
    BufferedOutputStream out=new BufferedOutputStream(System.out);
    int low=0;
    int high=a.length;
    while(low!=high){
        int mid=(low+high)/2;
        if(a[mid]<x){
            low=mid+1;
        }
        else{
            high=mid;
        }
    }
    long ans=L[low]+x-1;   
    if(low!=0){
    ans=L[low]+x-a[low-1]-1;
    }

     return ans;



}

Answer 1

这种技术：

low + (high - low) /2

主要用于避免整数溢出。

由于mid是一个数值类型的实例，所以它对它所能容纳的值有一个上限。低值和高值之和可能会超过这个最大值，导致溢出和不可预测的结果。即使low和high都是合法值（即正值和high>=low)，也会发生这种情况。

int low = 1170105034
int high = 1347855270
(low + high) / 2 //outputs  -888503496
low + (high - low) / 2 //outputs 1258980152