user3165873 user3165873 - 1 year ago 61
C Question

Implementing strictly lower bound in C

I have come up with this solution to implement strictly lower bound in a sorted array:

long lowerBound(long key, long size, long *a){
long low = 0, high = size, mid;
if(a[low] >= key){
return -1;
while(low < high){
mid = (low+high)/2;
if(a[mid] >= key){
high = mid - 1;
} else{
low = mid;
return low;

But this does not seem to work. It fails at some test cases. For example:

A[7] = {0, 1, 1, 3, 5, 5, 10}

key = 4

It enters an infinite loop.

Here is the test run:

After first iteration:
low = 3, high = 7, mid = 3

After second iteration:
low = 3, high = 4, mid = 5

After third iteration:
low = 3, high = 4, mid = 3.
Then it get stuck.

Can anyone point me in right direction. Thanks in advance!!

Answer Source

It gets "stuck" because when your low equals high - 1, mid becomes low: (low+low+1)/2 == low, then a[mid] >= key is false and mid sets to low again. You need to set low to mid + 1 if a[mid] < key and set high to mid otherwise. Then you will find the first occurrence of key or, if there is no element, equal to key, the first occurrence of the element that is greater than key, and, if all the elements are less than key, you will get the initial value of high.

UPD: And, since it's binary search, you will always get low == high - 1. Keep it in mind next time!

UPD2: And one more thing! It would be better to use mid = low+((high-low)/2), because this prevents some overflow errors.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download