code: private static int binarySearch(int[] a, int start, int end, int key) {
          int lo = start, hi = end-1; // search range is [lo,hi]
  
          // invariant lo<=hi
          while (lo <= hi) {
              int pivot = (lo + hi)/2;
              int v = a[pivot];
  
              if (v < key)        // needs to search upper half
                  lo = pivot+1;
              else if (v > key)   // needs to search lower half
                  hi = pivot-1;
              else    // eureka!
                  return pivot;
          }
          return -(lo + 1); // insertion point
      }
docs: Switch to {@code java.util.Arrays.binarySearch} when we depend on Java6.