Package com.google.mu.collect

Class BinarySearch.Table<K,C extends Comparable<C>>

java.lang.Object
com.google.mu.collect.BinarySearch.Table<K,C>
Type Parameters:
K - the search key, usually a target value, but can also be a target locator object like BinarySearch.IntSearchTarget.
C - the binary search result, usually the index in the source array or list, but can also be the optimal solution in non-array based bisection algorithms such as the minimum value of a parabola function.
Enclosing class:
BinarySearch
public abstract static class BinarySearch.Table<K,C extends Comparable<C>> extends Object
Like a hash table, allows looking up comparable values by a key, except the lookup is through binary search instead of hashing.

  • Method Details

    • find

      public Optional<C> find(K target)
      Searches for target and returns the result if found; or else returns empty.

      This is an O(logn) operation.

    • rangeOf

      public com.google.common.collect.Range<C> rangeOf(K target)
      Finds the range of elements that match target.

      If the target is found at index i, the single-element range [i..i] is returned.

      If there are ties from index i to j, the closed range [i..j] is returned.

      If the target isn't found, an empty range is returned whose endpoint is the "insertion point" (where the target would have been inserted without breaking order). The direction of the open endpoint determines whether to insert before or after the point.

      Invariants for insertion points:

      • An open lower endpoint (i.. means target > i so the insertion point should be after i in order not to break order.
      • An open upper endpoint ..j) means target < j so the insertion point should be before j in order not to break order.
      • A closed lower or upper endpoint means target >= i or target <= j respectively, so the insertion point can be either before or after without breaking order.

      Therefore:

      • For all insertion points except the last one after MAX_VALUE, the returned range is closed-open [i..i), indicating that the insertion point is immediately before endpoint i.
      • While if the insertion point is after MAX_VALUE, the returned range is open-closed (MAX_VALUE..MAX_VALUE], indicating that the insertion point is immediately after endpoint MAX_VALUE.

      If your code needs the insertion point when not found, but doesn't need to find the range of elements otherwise, use insertionPointFor(K) instead, which is more intuitive and also faster.

      Realistically though, unless target > MAX_VALUE is meaningful to your use case, it's okay to simply insert the target before rangeOf().lowerEndpoint(). This invariant holds regardless whether the target is found or not.

      This is an O(logn) operation.

    • insertionPointFor

      public abstract InsertionPoint<C> insertionPointFor(K target)
      Finds the InsertionPoint if target were to be added in order.

      Specifically, if target is found, the insertion point is at the its index; while if not found, the insertion point is between the two adjacent indexes where it could be inserted.

      Imagine in a Google Doc page, if you have two columns of texts to be rendered into a two-column table, and you want to split the two columns as evenly as possible such that it takes the fewest number of lines overall. you can implement it with binary search: 

      
   InsertionPoint optimal = BinarySearch.forInts(Range.closedOpen(1, tableWidth))
       .insertionPointFor(
           (low, w, high) ->
               Integer.compare(
                   renderWithColumnWidth(text1, w),
                   renderWithColumnWidth(text2, tableWidth - w)));
   return optimal.exact()
       .orElseGet(
           () -> {
             int lines1 = max(
                 renderWithColumnWidth(text1, optimal.floor()),
                 renderWithColumnWidth(text2, tableWidth - optimal.floor()));
             int lines2 = max(
                 renderWithColumnWidth(text1, optimal.ceiling()),
                 renderWithColumnWidth(text2, tableWidth - optimal.ceiling()));
             return lines1 < lines2 ? floor : ceiling;
           });

      This is an O(logn) operation.

    • insertionPointBefore

      public abstract InsertionPoint<C> insertionPointBefore(K target)
      Finds the insertion point immediately before the first element that's greater than or equal to the target.

      If target is absent, insertionPointBefore(K) and insertionPointAfter(K) will be the same point, after the last element less than the target and the first element greater than it.

      insertionPointBefore(target).exact() will always return empty.

      This is an O(logn) operation.

    • insertionPointAfter

      public abstract InsertionPoint<C> insertionPointAfter(K target)
      Finds the insertion point immediately after the last element that's less than or equal to the target.

      If target is absent, insertionPointBefore(K) and insertionPointAfter(K) will be the same point, after the last element less than the target and the first element greater than it.

      insertionPointAfter(target).exact() will always return empty.

      This is an O(logn) operation.

    • by

      public final <Q> BinarySearch.Table<Q,C> by(Function<Q,? extends K> keyFunction)
      Returns a new BinarySearch.Table over the same source but transforms the search target using the given keyFunction first.

      Useful for creating a facade in front of a lower-level backing data source.

      For example, if you have epoch millisecond timestamps stored in a sorted long[] array, you can wrap it as a BinarySearch.Table<Instant, Integer> for your code to be able to search by Instant repeatedly: 

      
 class Timeline {
   private final long[] timestamps;

   BinarySearch.Table<Instant, Integer> instants() {
     return BinarySearch.inSortedArray(timestamps).by(Instant::toEpochMilli);
   }
 }

      This is an O(1) operation.

      Type Parameters:
      Q - the logical search key type of the returned BinarySearch.Table.