Six classic binary-search mistakes, each reproduced
===================================================

1. hi = a.length with lo <= hi, searching [1, 3, 5] for 9
   java.lang.ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3
   correct version returns -1

2. lo = mid instead of lo = mid + 1, searching [1, 2] for 2 (stopped after 6 iterations)
   iteration 1: low=0 high=1 mid=0 a[mid]=1
   iteration 2: low=0 high=1 mid=0 a[mid]=1
   iteration 3: low=0 high=1 mid=0 a[mid]=1
   iteration 4: low=0 high=1 mid=0 a[mid]=1
   iteration 5: low=0 high=1 mid=0 a[mid]=1
   iteration 6: low=0 high=1 mid=0 a[mid]=1
   correct version returns 1

3. unsorted input [5, 1, 2, 9, 3], key 3
   binary search returns -1, a linear scan returns 4

4. duplicates [1, 2, 2, 2, 2, 2, 3], key 2 occurs at indexes 1..5
   iterative returns 3, Arrays.binarySearch returns 3, firstOccurrence returns 1, lastOccurrence returns 5

5. Arrays.binarySearch does not return -1 for "not found": it returns -(insertion point) - 1
   Arrays.binarySearch([10, 20, 30, 40, 45], 25) = -3   (== -1? false)   insertion point = 2
   Arrays.binarySearch([10, 20, 30, 40, 45], 5) = -1   (== -1? true)   insertion point = 0
   Arrays.binarySearch([10, 20, 30, 40, 45], 50) = -6   (== -1? false)   insertion point = 5

6. overflow of (lo + hi) / 2: see 03-overflow-mid.txt
