Deciding mid in binary search

Question

I was practising a questions on hackerearth :

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

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

int mid=(low+high)/2

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)

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:These were practise questions and solved now (by me)

Code1

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

}

Code2

    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;



}

amrender singh · Accepted Answer · 2018-06-11 17:53:49Z

3

This technique :

low + (high - low) /2

is mainly used to avoid integer overflow.

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

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

Example:

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

answered Jun 11, 2018 at 17:53

amrender singh

8,2594 gold badges27 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Dhruv Bhagat Over a year ago

Hello,Amrender I agree to your point and appreciate your effort but my main questions isn't this ,what I really mean is sometimes to get the correct answer we have to do (low+high)/2 and sometimes low +(high-low+1)/2 works For instance consider low=4,high=5, mid=(low+high)/2 will repeatedly get stuck in code1 but low+(high-low+1)/2 would produce correct answer in such case whereas (low+high)/2 is good enough for code2 to get me the correct answer, consider that integer overflow is not a problem and please clarify this thing. Thanks

amrender singh Over a year ago

@DhruvBhagat Correct way of calculating mid for second case is low +(high-low)/2. So now evaluate both the expressions. when low = 4, high = 5, . (low+high)/2 = (4+5)/2 = > 4. Whereas expression two produces - > low + (high-low)/2 = 4 + (5-4)/2 = > 4. Both the expressions produce the same answer. In coming back to your original question, Try updating the later one in your hackerank solution and all your test cases will pass.

Collectives™ on Stack Overflow

Deciding mid in binary search

Code1

Code2

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

Code1

Code2

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related