MeteredBinarySearcher

// ===============================================================
// "Keep it simple, stupid" ... a design principle noted by the
// U.S. Navy in 1960
//                                    - WIKIPEDIA (Kiss principle)
//
//
// Binary search. ... Simpler approaches are doomed to failure!
//
//              - KNUTH (The Art of Computer Programming 3 6.2.1.)
//
//
// Mama says, "Stupid is as stupid does."
//                                        - FORREST (Forrest Gump)
// ===============================================================

class MeteredBinarySearcher<T extends Comparable<T>>
extends MeteredSearcher<T> {

  private int loop(T[] seq, T key, int low, int high) { 
    while (tick() && low <= high) {
      int middle = low + ((high - low) >> 1);
      int ordering = key.compareTo(seq[middle]);
      if (ordering < 0) {
        high = middle - 1;
      }
      else if (ordering > 0) {
        low = middle + 1;
      }
      else {
        return middle;
      }
    }
    return fail;
  }

  private int recurse(T[] seq, T key, int low, int high) {
    if (tick() && low > high) {
      return fail;
    }
    int middle = low + ((high - low) >> 1);
    int ordering = key.compareTo(seq[middle]);
    if (ordering < 0) {
      return recurse(seq, key, low, middle - 1);
    }
    else if (ordering > 0) {
      return recurse(seq, key, middle + 1, high);
    }
    else {
      return middle;
    }
  }

  public int maneuver(T[] seq, T key, int from, int to) {
    return (from < to) ?
      loop(seq, key, from, to) :
      recurse(seq, key, to, from);
  }
}