5

I've read multiple articles including Jon Bentleys chapter on binary search. This is what I understand about CORRECT binary search logic and it works in the simple tests I did:

binarysearch (arr, low, high, k)
    1. while (low < high)
        2. mid  = low + (high - low)/2
        3. if (arr[mid] == k)
               return mid
        4. if (arr[mid] < k )
               high = mid -1
        5. else 
               low = mid + 1

Now to find the 1st occurence with sorted duplicates, you'd chance line 3 if condition to continue instead of returning mid as 

binarysearch_get_first_occur_with_duplicates (arr, low, high, k)
    1. while (low < high)
        2. mid  = low + (high - low)/2
        3. if (arr[mid] == k)
               high = mid - 1
               low_so_far = arr[mid]
        4. if (arr[mid] < k )
               high = mid -1
        5. else 
               low = mid + 1
        return low_so_far

Similarly to get highest index of repeated element, you'd do low = mid + 1 and continue if arr[mid]==k

This logic seems to be working but in multiple places I see the loop invariant as 

while (low + 1 < high)

I am confused and want to understand when you might want to use low + 1 < high instead of low < high.

In the logic I described above low + 1 < high condition leads to errors if you test with simple example.

Can someone clarify why and when we might want to use low + 1 < high in the while loop instead of low < high?

Daniel Daranas
  • 22,454
  • 9
  • 63
  • 116
user2664398
  • 65
  • 4
  • At a guess, if your invariant is that the target must lie in `low <= i <= high`, then you use `while (low < high)`; if your invariant is that the target must lie in `low <= i < high` then you use `while (low + 1 < high)`. Having said that, I haven't checked it! – Rafe Aug 12 '13 at 07:21
  • @Rafe Your guess is correct. Go ahead and post it as an answer. – David Eisenstat Aug 12 '13 at 11:30

1 Answers1

4

If your invariant is that the target must lie in low <= i <= high, then you use while (low < high); if your invariant is that the target must lie in low <= i < high then you use while (low + 1 < high). [Thanks to David Eisenstat for confirming this.]

Rafe
  • 5,237
  • 3
  • 23
  • 26