Programming Pearls: Column 9.3 Binary Search - range initialization

Question

In Section 9.3 Job Bentley presents a modified binary search..

a brief snip of the typical implementation and the better approach shown in 9.3

if (arr[mid] < key) low = mid+1
else if (arr[mid] > key) high = mid-1
else return mid;

modified/efficient comparison with a different invariant..

if (arr[mid] < key) low = m;
else high = m;

And outside the loop there is a check if the key at the index 'high'. In the modified binary search the left index 'low' starts at -1 (instead of 0) and 'high' index starts at n (instead of n-1).. and the loop runs

while (low + 1 != high)

This modified search seems to work even if I set low = 0 and high = n-1.

But I would rather not second guess Job Bentley in his code. So why is he setting low to -1 and high to n ? Is there any corner case where only this will work ?

Answer 1

If you have an array that is empty (n == 0), then a check of while(low + 1 != high) will only correctly terminate if low begins at -1 and high at 0.

while((-1 + 1) != 0) //true

If low began at 0 instead, or high began at -1 (or both), then the loop will clearly perform at least one check:

• while((0 + 1) != 0) // false
• while((-1 + 1) != -1) // false
• while((0 + 1) != -1) // false

That one check on an empty array will likely access an out of bounds index, which invokes undefined behavior.