Sunday, February 19, 2017

MeteredQuickLinearSearcher

// ===============================================================
// Put an Elephant in Cairo, to wit put the key in the last place
// you'd look.
// ===============================================================
 
class MeteredQuickLinearSearcher<T extends Comparable<T>>
extends MeteredSearcher<T> {

  public int maneuver(T[] seq, T key, int from, int to) {
 
    int step = from < to ? 1 : -1;
    T bumpedValue = seq[to];
    seq[to] = key;

    int i = from;
    while (tick() && key.compareTo(seq[i]) != 0) {
      i += step;
      tick();
    }
    seq[to] = bumpedValue;
    return tick() && key.compareTo(seq[i]) == 0 ? i : fail;
  }
}