LinearSearch { public static <T> int linearSearch(List<? extends T> list, Comparator<T> comparator, T key, int initialGuess) { int guess = initialGuess; if (guess >= list.size()) { guess = list.size()-1; } int comparison = comparator.compare(list.get(guess), key); if (comparison == 0) { return guess; } if (comparison < 0) { guess++; while (guess < list.size()) { comparison = comparator.compare(list.get(guess), key); if (comparison == 0) { return guess; } if (comparison > 0) { return -(guess+1); } guess++; } return -(list.size()+1); } else { guess--; while (guess >= 0) { comparison = comparator.compare(list.get(guess), key); if (comparison == 0) { return guess; } if (comparison < 0) { return -(guess+2); } guess--; } return -1; } }  static int linearSearch(List<? extends T> list, Comparator<T> comparator, T key, int initialGuess);  }
@Test public void testLinearSearch() { List<Integer> list = Lists.newArrayList(0, 1, 3, 4); doTest(list, 5, 10); doTest(list, 5, 4); doTest(list, 5, 3); doTest(list, 5, 2); doTest(list, 5, 1); doTest(list, 5, 0); doTest(list, 4, 10); doTest(list, 4, 4); doTest(list, 4, 3); doTest(list, 4, 2); doTest(list, 4, 1); doTest(list, 4, 0); doTest(list, 3, 10); doTest(list, 3, 4); doTest(list, 3, 3); doTest(list, 3, 2); doTest(list, 3, 1); doTest(list, 3, 0); doTest(list, 2, 10); doTest(list, 2, 4); doTest(list, 2, 3); doTest(list, 2, 2); doTest(list, 2, 1); doTest(list, 2, 0); doTest(list, 1, 10); doTest(list, 1, 4); doTest(list, 1, 3); doTest(list, 1, 2); doTest(list, 1, 1); doTest(list, 1, 0); doTest(list, 0, 10); doTest(list, 0, 4); doTest(list, 0, 3); doTest(list, 0, 2); doTest(list, 0, 1); doTest(list, 0, 0); doTest(list, -1, 10); doTest(list, -1, 4); doTest(list, -1, 3); doTest(list, -1, 2); doTest(list, -1, 1); doTest(list, -1, 0); }