MeteredQuickerLinearSearcher

// ===============================================================
// Look twice before you leap two steps.
// ===============================================================

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

  public int maneuver(T[] seq, T key, int from, int to) {

    int step = from < to ? 1 : -1;
    int leap = 2 * step;
    T bumpedValue = seq[to];
    seq[to] = key;

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