When to use low <high ​​or low + 1 <high ​​for cycle invariant

Question

I read several articles, including John Bentlis's binary search chapter. This is what I understand about the CORRECT binary search logic and works in simple tests that 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 place with sorted duplicates, you will get a random row of 3 if the continuation condition instead of returning in the middle

 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 the highest index of a repeating element, you must do low = mid + 1 and continue if arr[mid]==k

This logic seems to work, but in a few places I see the loop invariant as

 while (low + 1 < high) 

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

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

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

Answer 1

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