CODEWITHSUNDEEP
algorithmbinary-search
Ayush Goyal
Ayush Goyal

Reputation: 439

Infinite Loop in Modified Binary Search

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?

Upvotes: 0

Views: 184

Answers (1)

Lee.O.
Lee.O.

Reputation: 73

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

Upvotes: 0

Related Questions