algorithm - 在二进制搜索中确定中间值

Question

我在 hackerearth 上练习一道题:

https://www.hackerearth.com/practice/algorithms/searching/binary-search/practice-problems/algorithm/monk-and-special-integer-code-monk/

在这个问题中，我写了一个二进制搜索代码，我用过的地方:

int mid=(low+high)/2

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

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

我的问题是我们如何决定我们将如何选择中间？

PS:这些是练习题，现在(由我)解决了

代码1

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);

}

代码2

    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 的总和可能会超过此最大值，从而导致溢出和不可预测的结果。即使 low 和 high 都是合法值(即正值和 high >= low)，也会发生这种情况。

对于 high 和 low 的合法值，表达式 mid = low + (high - low)/2 永远不会溢出，并且始终会给出所需的结果。

例子:

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