Package com.google.mu.collect

Class BinarySearch

java.lang.Object
com.google.mu.collect.BinarySearch
@RequiresGuava public final class BinarySearch extends Object
Generic binary search algorithm with support for and beyond sorted lists and arrays, in a fluent API.

For sorted lists and arrays: 


 BinarySearch.inSortedArray([10, 20, 30, 40]).find(20)
     => Optional.of(1)

 // Find the insertion point if not found
 BinarySearch.inSortedList([10, 20, 30, 40]).insertionPointFor(22)
     => InsertionPoint.before(2)

 // Search for double with a tolerance factor
 // And find the range of all matches
 BinarySearch.inSortedArrayWithTolerance([1.1, 2.1, 2.2, 2.3, 3.3, 4.4], 0.5).rangeOf(2)
     => Range.closed(1, 3)
To solve a monotonic polynomial function: 

 double polynomial(double x) {
   return pow(x, 3) + 3 * x;
 }

 InsertionPoint<Double> solve(double y) {
   return BinarySearch.forDoubles()
       .insertionPointFor((low, mid, high) -> Double.compare(y, polynomial(mid)));
 }
To find the minimum int value of a parabola: 

 double parabola(int x) {
   return pow(x, 2) + 4 * x - 3;
 }

 int minimum = BinarySearch.forInts()
     .insertionPointFor(
         (low, mid, high) -> Double.compare(parabola(mid - 1), parabola(mid)))
     .floor();
     => -2
To emulate the Guess The Number game: 

 BinarySearch.forInts()
     .find((lo, mid, hi) -> tooHighOrTooLow(mid))
     => Optional.of(theGuessedNumber)

The forInts(), forLongs(), forDoubles() and the primitive array search methods perform no boxing in the O(logn) search operation.

Note that except inSortedList(List, Comparator), which may support null search targets if the comparator supports nulls, no other BinarySearch.Table implementations allow null search targets.

Since:
8.0

  • Method Details

    • inSortedList

      public static <E extends Comparable<E>> BinarySearch.Table<E,Integer> inSortedList(List<? extends E> list)
      Returns a BinarySearch.Table to search for element indexes in the given sorted list.

      For example: inSortedList(numbers).find(20).

      This is an O(1) operation.

      Parameters:
      list - expected to support random access (not LinkedList for instance), or else performance will suffer.

    • inSortedList

      public static <E> BinarySearch.Table<E,Integer> inSortedList(List<? extends E> list, Comparator<? super E> sortedBy)
      Returns a BinarySearch.Table to search for element indexes in the given sorted list according to comparator.

      For example: inSortedList(timestamps, nullsFirst(naturalOrder())).find(timestamp).

      This is an O(1) operation.

      Parameters:
      list - expected to support random access (not LinkedList for instance), or else performance will suffer.

    • inSortedList

      public static <Q extends Comparable<Q>, E> BinarySearch.Table<Q,Integer> inSortedList(List<? extends E> list, Function<? super E,? extends Q> sortedBy)
      Returns a BinarySearch.Table to search for element indexes in the given list sorted by the sortBy function.

      For example: inSortedList(employees, Employee::age).rangeOf(20).

      This is an O(1) operation.

      Parameters:
      list - expected to support random access (not LinkedList for instance), or else performance will suffer.

    • inSortedArray

      public static BinarySearch.Table<Integer,Integer> inSortedArray(int[] array)
      Returns a BinarySearch.Table to search for array element indexes in the given sorted int array.

      For example: inSortedArray(numbers).find(20).

      This is an O(1) operation.

    • inSortedArray

      public static BinarySearch.Table<Long,Integer> inSortedArray(long[] array)
      Returns a BinarySearch.Table to search for array element indexes in the given sorted long array.

      For example: inSortedArray(largeNumbers).find(1000000000000L).

      This is an O(1) operation.

    • inSortedListWithTolerance

      public static BinarySearch.Table<Double,Integer> inSortedListWithTolerance(List<Double> list, double tolerance)
      Returns a BinarySearch.Table to search for element indexes in the given list of sorted double values. The positive tolerance is respected when comparing double values.

      For example: inSortedListWithTolerance(temperatures, 0.1).find(30).

      This is an O(1) operation.

      Parameters:
      list - expected to support random access (not LinkedList for instance), or else performance will suffer.
      tolerance - an inclusive upper bound on the difference between the search target and elements in the list, which must be a non-negative finite value, i.e. not Double.NaN, Double.POSITIVE_INFINITY, or negative, including -0.0

    • inSortedArrayWithTolerance

      public static BinarySearch.Table<Double,Integer> inSortedArrayWithTolerance(double[] array, double tolerance)
      Returns a BinarySearch.Table to search for array element indexes in the given sorted double array. The positive tolerance is respected when comparing double values.

      For example: inSortedArrayWithTolerance(temperatures, 0.1).find(30).

      This is an O(1) operation.

    • forInts

      public static BinarySearch.Table<BinarySearch.IntSearchTarget,Integer> forInts()
      Returns a BinarySearch.Table over all integers.

      Callers can search by an BinarySearch.IntSearchTarget object that will be called at each probe to determine whether the target is already found at the current mid-point, to the left half of the current subrange, or to the right half of the current subrange.

      This is an O(1) operation.

    • forInts

      public static BinarySearch.Table<BinarySearch.IntSearchTarget,Integer> forInts(com.google.common.collect.Range<Integer> range)
      Returns a BinarySearch.Table over the given range.

      Callers can search by an BinarySearch.IntSearchTarget object that will be called at each probe to determine whether the target is already found at the current mid-point, to the left half of the current subrange, or to the right half of the current subrange.

      While the common use cases of binary search is to search in sorted arrays and lists, there are diverse contexts where the algorithm is also applicable (think of the Guess the Number game). As a more realistic example, you can binary search a rotated, otherwise strictly-ordered array, using the following code: 

       
 Optional<Integer> binarySearchRotated(int[] rotated, int target) {
   return BinarySearch.forInts(Range.closedOpen(0, rotated.length))
       find((low, mid, high) -> {
         int probe = rotated[mid];
         if (target < probe) {
           return rotated[low] <= probe && target < rotated[low] ? 1 : -1;
         } else if (target > probe) {
            return probe <= rotated[high] && target > rotated[high] ? -1 : 1;
         } else {
           return 0;
         }
       });
 }

      This is an O(1) operation.

    • forLongs

      public static BinarySearch.Table<BinarySearch.LongSearchTarget,Long> forLongs()
      Similar to forInts(), but returns a BinarySearch.Table over all long integers.

      Callers can search by a BinarySearch.LongSearchTarget object that will be called at each probe to determine whether the target is already found at the current mid-point, to the left half of the current subrange, or to the right half of the current subrange.

      For example, if we are to emulate the "Guess The Number" game, there will be a secret number and we can bisect the full long integer domain to find the number as in: 

      
 Optional<Long> guessed = forLongs().find((low, mid, high) -> Integer.compare(secret, mid));
 assertThat(guessed).hasValue(secret);

      This is an O(1) operation.

    • forLongs

      public static BinarySearch.Table<BinarySearch.LongSearchTarget,Long> forLongs(com.google.common.collect.Range<Long> range)
      Similar to forInts(Range), but returns a BinarySearch.Table over the given range of long integers.

      Callers can search by a BinarySearch.LongSearchTarget object that will be called at each probe to determine whether the target is already found at the current mid-point, to the left half of the current subrange, or to the right half of the current subrange.

      This is an O(1) operation.

    • forDoubles

      public static BinarySearch.Table<BinarySearch.DoubleSearchTarget,Double> forDoubles()
      Returns a BinarySearch.Table over all finite double values (except Double.NaN, Double.NEGATIVE_INFINITY and Double.POSITIVE_INFINITY).

      Callers can search by an BinarySearch.DoubleSearchTarget object that will be called at each probe to determine whether the target is already found at the current mid-point, to the left half of the current subrange, or to the right half of the current subrange.

      Different from inSortedArrayWithTolerance(double[], double), which is to search within the int indexes of a double array, this method searches through double values.

      You can use binary search to solve monotonic functions. For example the following method solves cube root: 

      
 BinarySearch.Table<Double, Double> cubeRoot() {
   return forDoubles()
       .by(cube -> (low, mid, high) -> Double.compare(cube, mid * mid * mid));
 }

 cubeRoot().insertionPointFor(125.0) => InsertionPoint.at(5.0)

      This is an O(1) operation.

    • forDoubles

      public static BinarySearch.Table<BinarySearch.DoubleSearchTarget,Double> forDoubles(com.google.common.collect.Range<Double> range)
      Similar to forInts(Range), but returns a BinarySearch.Table over the given range of double precision numbers.

      Callers can search by a BinarySearch.DoubleSearchTarget object that will be called at each probe to determine whether the target is already found at the current mid-point, to the left half of the current subrange, or to the right half of the current subrange.

      For example you can implement square root through binary search: 

      
 BinarySearch.Table<Double, Double> sqrt() {
   return forDoubles(atLeast(0D))
       .by(square -> (low, mid, high) -> Double.compare(square, mid * mid));
 }

 sqrt().insertionPointFor(25.0) => InsertionPoint.at(5.0)

      Infinite endpoints are disallowed.

      This is an O(1) operation.