BinarySearch Explained - google/mug GitHub Wiki

The JDK offers binary search algorithms out of the box, for sorted arrays and lists.

The Mug BinarySearch class (it requires Guava dependency) is a generalization applicable to more use cases. For example:

• You may want to search in a double array with a tolerance factor.

  Optional<Integer> index =
      BinarySearch.inSortedArrayWithTolerance(doubles, 0.0001).find(3.14)

• Or search for the range of indexes when the array can have duplicates (at least according to the tolerance factor).

  Range<Integer> indexRange =
      BinarySearch.inSortedArrayWithTolerance(doubles, 0.0001).rangeOf(3.14)

• Or search for the solution to a monotonic polynomial equation (the kind of fun trick you might have done once or twice in interviews).

  long polynomial(int x) {
    return 5 * x * x * x + 3 * x + 2;
  }
  
  Optional<Integer> solvePolynomial(long y) {
    return BinarySearch.forInts()
        .find((low, x, high) -> Long.compare(y, polynomial(x));
  }