CODEWITHSUNDEEP
searchbinary
LCP
LCP

Reputation: 71

Binary search to search element greater than or equal to a given key

my code snippet is:

int bs_greaterthan_or_equal(int *a, int key, int low, int high) {
    while(low<high) {
    int mid = low +(high-low)/2.0;
    if(a[mid]<key) {
    low = mid + 1;
    }
    else high = mid;
    }

    return high;
}

But even when i search a number greater than last element in the array it returns the last index

e.g a[] = {1,3,10,15,20,25,27} key = 28 It returns 7

Upvotes: 2

Views: 7497

Answers (1)

user162417
user162417

Reputation: 51

But even when i search a number greater than last element in the array it returns the last index

Because that is what it has been designed to do. Technically speaking, it returns the last index + 1.

Notice the condition:

if(a[mid]<key) {
low = mid + 1;
}

When looking for an element that's larger than (or equal to) the last element of the array, the above condition will always evaluate to true. The loop terminates when you reach the last element itself, where low is set to one more than the last index.

When you search for the key 28 in your example, low is repeatedly updated because the above condition always evaluates to true. When mid equals 6, then a[mid] is still lesser than 28, so low is set to mid + 1, i.e 7. At this point, low and high become equal (notice that high was never modified) and the loop terminates. The function returns 7.

If there's something specific that you wish to return (say, -1) upon searching for a number that's greater than or equal to the last element in the array, you can modify your code as follows. 

int bs_greaterthan_or_equal(int *a, int key, int low, int high) {
    int max_limit = high;
    while(low<high) {
    int mid = low +(high-low)/2.0;
    if(a[mid]<key) {
    low = mid + 1;
    }
    else high = mid;
    }

    return high == max_limit ? -1 : high;
}

If the array contains a larger or equal element for the given key, high will store its index. Otherwise, at the end, high will remain equal to max_limit, meaning that the search procedure couldn't find such an element, and hence, will return -1.

Upvotes: 2

Related Questions