Infinite Loop in Modified Binary Search

Question

I am trying to implement a modified version of Binary Search which returns the position of the next greatest value from a given key , from a sorted array.

Here's the code -- (lli refers to long long int)

lli search(vector<lli>arr,lli key)
{
    lli low=0,high=arr.size() - 1,mid,pos=-1;

    while(low<=high)
    {
        mid=low + (high-low)/2;

         if(arr[mid]<key)
            low=mid+1;
        else{
                pos=mid;
                high=mid-1;
            }
    }
    return pos;
}

Here arr is the sorted array and we have to find the position of the next greatest element than the key in the array arr.

I have taken care that the key is between [min(arr),max(arr)].So, pos will have a value in [0 ,arr.size() - 1] .

The method runs for many values I can think of but the online judge rejects it with Time Limit Exceeded error. Is there an infinite loop possible here?

Why are you calculating the mid in that way? Is that how you intended to modify the binary search? — Alex S
– Alex S, Commented May 22, 2017 at 18:41
@AlexS high and low are values upto 10^9 so adding them for mid = (high+low)/2 can cause problems. — Ayush Goyal
– Ayush Goyal, Commented May 22, 2017 at 18:42

Lee.O. · Accepted Answer · 2017-05-22 18:58:15Z

0

you can solve as a regular binary search but use

if (arr[mid] == key){
    if (mid == arr.size() - 1)
         return -1; // key was the last element, there is nothing after it
    return mid + 1;
}

answered May 22, 2017 at 18:58

Lee.O.

735 bronze badges

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

Collectives™ on Stack Overflow

Infinite Loop in Modified Binary Search

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related