user3165873 - 2 months ago 10

C Question

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

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.

Source (Stackoverflow)

Comments