If an element is not present in an array how to find lower bound of the element using binary search

input: array size, element

5 4

array elements:

1 2 3 7 8

output: 2 [which is the index of lower bound]

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

    if(a[mid] < s){
        low = mid   1;
    }  
    else if(a[mid] >= s){
        high = mid - 1;
    }
}

testcases 1 testcases 2

CodePudding user response：

I won't provide code for what I believe to be homework. But I will offer advice because you have to be careful to get the edge cases on binary search right. It took many years for anyone to produce a correct implementation, most textbook solutions were wrong for a shocking amount of time, and most professional programmers struggle with this one.

I have found it very helpful to distinguish between three variations on binary searches. They can be coded like this:

-- Version 1.
while (low < high) {
    int mid = (low   high) / 2;
    if (some condition on mid) {
        low = mid;
    } else {
        high = mid-1;
    }
}

-- Version 2.
while (low < high) {
    int mid = (low   high) / 2;
    if (some condition on mid) {
        low = mid 1;
    } else {
        high = mid;
    }
}

-- Version 3.
while (low <= high) {
    int mid = (low   high) / 2;
    if (lower bound condition on mid) {
        low = mid 1;
    } else if (upper bound condition on mid) {
        high = mid-1;
    }
    else {
        break, return, or otherwise indicate we have an answer
    }
}

The first two versions wind up with low == high == the only possible answer. Which one to use requires careful thought about what condition told you about mid.

The third version is for searching for a specific value in the array. This is a specific but important case, however MOST of my binary searches don't look like that.

Now in your case you need 2 searches. The first is to find the LAST index whose value is a lower bound. And the second to find the index of the FIRST time that value appears. I don't think I'm giving too much away to say that I wouldn't write those the same way.

Good luck, and hopefully this problem causes you to better understand binary search by the time you are done!