// Search for value in items[lo..hi].  Return a value k such that
  // everything in items[lo..k] is <= value according to compareTo
  // and everything in items[k+1..hi] is greater than value.  Either
  // of these regions might be empty, so if everything in items[lo..hi]
  // is greater than value, we return lo-1, and if everything is less
  // than or equal to value, then we return hi.
  // pre: items is sorted in ascending order and lo<=hi.
  // Uses binary search.
  private int bsearch(int lo, int hi, String value) {
    int L = lo-1;
    int R = hi+1;
    while (L+1 != R) {
      // invariant: items[lo..L] <= value && items[R..hi] > value.
      // the region items[L+1..R-1] has not been searched yet
      int mid = (L+R) / 2;
      if (items[mid].compareTo(value) <= 0) {
        L = mid;
      } else {
        R = mid;
      }
    }
    //post: If L>=lo, then L is the largest value such that items[L]<=value
    //      (so if value is present in the list, items[L] equals value.)
    return L;
  }