Lists { public static <T> int bisectLeft(@NonNull List<T> list, @NonNull Comparator<T> ordering, @NonNull T item) { int low = 0; int high = list.size(); int mid; while (low < high) { mid = (low + high) / 2; if (ordering.compare(item, list.get(mid)) <= 0) { high = mid; } else { low = mid + 1; } } return low; } private  Lists(); @NonNull static List<T> map(@NonNull  List<S> source, @NonNull Function<S, T> transformation); static int bisectLeft(@NonNull List<T> list, @NonNull Comparator<T> ordering, @NonNull T item);  }
@Test public void bisectLeft_singleton() { List<String> list = new ArrayList<>(); list.add("b"); assertEquals(0, Lists.bisectLeft(list, ordering, "a")); assertEquals(0, Lists.bisectLeft(list, ordering, "b")); assertEquals(1, Lists.bisectLeft(list, ordering, "c")); }
@Test public void bisectLeft_withRuns() { List<String> list = new ArrayList<>(); list.add("b"); list.add("b"); list.add("d"); list.add("d"); list.add("d"); list.add("e"); list.add("f"); list.add("f"); assertEquals(0, Lists.bisectLeft(list, ordering, "a")); assertEquals(0, Lists.bisectLeft(list, ordering, "b")); assertEquals(2, Lists.bisectLeft(list, ordering, "c")); assertEquals(2, Lists.bisectLeft(list, ordering, "d")); assertEquals(5, Lists.bisectLeft(list, ordering, "e")); assertEquals(6, Lists.bisectLeft(list, ordering, "f")); assertEquals(8, Lists.bisectLeft(list, ordering, "g")); }