时间戳

首页 > 解决方案 > 在二分搜索中确定中间值

algorithm - 在二分搜索中确定中间值

问题描述

我在hackerearth上练习一个问题：

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

在这个问题中，我编写了一个使用过的二进制搜索代码：

整数中间=（低+高）/2

我的循环卡在这里，所以在某些情况下我得到了 TLE。意识到问题（反复选择低）后，我将中间更改为低 +(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;



}

标签： algorithmbinary-search

解决方案

这种技术：

low + (high - low) /2

主要用于避免整数溢出。

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

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

例子：

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

推荐阅读