确定二进制搜索的中间 [英] Deciding mid in binary search

问题描述

我正在练习有关hackerearth的问题:

I was practising a questions on hackerearth :

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

In this question I had written a binary search code where I had used:

int mid =(低+高)/2

int mid=(low+high)/2

我的循环卡在这里，因此在某些情况下我获得了TLE的称号. 意识到问题(反复选择低电压) 我将中值更改为低+(高-低+1)/2，并以此更改了整个测试用例 通过了. (代码1)

My loop got stuck here and so I was getting TLE for some cases. Having realised the problem (that repeatedly low was being chosen) I changed the mid to low +(high-low+1)/2 and with this change whole test cases passed. (Code 1)

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

I had also done a similar problem where I had used (low+high)/2 and which also passed all the test cases.

我的问题是我们如何确定我们将如何选择中产呢?

My Question is how do we decide how are we gonna choose mid?

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

PS:These were practise questions and solved now (by me)

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;



}

推荐答案

此技术:

low + (high - low) /2

主要用于避免整数溢出.

is mainly used to avoid integer overflow.

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

Since mid is an instance of a numeric type, it has an upper limit on the value that it can hold. It is possible that the sum of low and high could exceed this maximum value, leading to overflow and unpredictable results. This can occur even if low and high are both legal values (i.e. both positive and high >= low).

对于高和低的合法值，表达式mid = low +(high-low)/2不会溢出，并且始终会提供所需的结果.

The expression mid = low + (high - low) / 2 will never overflow for legal values of high and low and will always give the desired result.

示例:

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

这篇关于确定二进制搜索的中间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！