https://github.com/google/guava/guava: Guava is a suite of core and expanded libraries that include utility classes, google's collections, io classes, and much much more. 
/*
 * Copyright (C) 2010 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
 * in compliance with the License. You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License
 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
 * or implied. See the License for the specific language governing permissions and limitations under
 * the License.
 */

package com.google.common.collect;

import static com.google.common.base.Preconditions.checkNotNull;

import com.google.common.annotations.Beta;
import com.google.common.annotations.GwtCompatible;
import com.google.common.base.Function;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.RandomAccess;
import org.checkerframework.checker.nullness.qual.Nullable;


Static methods pertaining to sorted List instances. 
In this documentation, the terms greatest, greater, least, and
lesser are considered to refer to the comparator on the elements, and the terms
first and last are considered to refer to the elements' ordering in a list.

Author:Louis Wasserman
/**
 * Static methods pertaining to sorted {@link List} instances.
 *
 * <p>In this documentation, the terms <i>greatest</i>, <i>greater</i>, <i>least</i>, and
 * <i>lesser</i> are considered to refer to the comparator on the elements, and the terms
 * <i>first</i> and <i>last</i> are considered to refer to the elements' ordering in a list.
 *
 * @author Louis Wasserman
 */
@GwtCompatible
@Beta final class SortedLists {
  private SortedLists() {}

  
A specification for which index to return if the list contains at least one element that
compares as equal to the key.

/**
   * A specification for which index to return if the list contains at least one element that
   * compares as equal to the key.
   */ enum KeyPresentBehavior {
    
Return the index of any list element that compares as equal to the key. No guarantees are
made as to which index is returned, if more than one element compares as equal to the key.

/**
     * Return the index of any list element that compares as equal to the key. No guarantees are
     * made as to which index is returned, if more than one element compares as equal to the key.
     */
    ANY_PRESENT {
      @Override
      <E> int resultIndex(
          Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) {
        return foundIndex;
      }
    },
    
Return the index of the last list element that compares as equal to the key. 
/** Return the index of the last list element that compares as equal to the key. */
    LAST_PRESENT {
      @Override
      <E> int resultIndex(
          Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) {
        // Of course, we have to use binary search to find the precise
        // breakpoint...
        int lower = foundIndex;
        int upper = list.size() - 1;
        // Everything between lower and upper inclusive compares at >= 0.
        while (lower < upper) {
          int middle = (lower + upper + 1) >>> 1;
          int c = comparator.compare(list.get(middle), key);
          if (c > 0) {
            upper = middle - 1;
          } else { // c == 0
            lower = middle;
          }
        }
        return lower;
      }
    },
    
Return the index of the first list element that compares as equal to the key. 
/** Return the index of the first list element that compares as equal to the key. */
    FIRST_PRESENT {
      @Override
      <E> int resultIndex(
          Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) {
        // Of course, we have to use binary search to find the precise
        // breakpoint...
        int lower = 0;
        int upper = foundIndex;
        // Of course, we have to use binary search to find the precise breakpoint...
        // Everything between lower and upper inclusive compares at <= 0.
        while (lower < upper) {
          int middle = (lower + upper) >>> 1;
          int c = comparator.compare(list.get(middle), key);
          if (c < 0) {
            lower = middle + 1;
          } else { // c == 0
            upper = middle;
          }
        }
        return lower;
      }
    },
    
Return the index of the first list element that compares as greater than the key, or 
list.size() if there is no such element. 
/**
     * Return the index of the first list element that compares as greater than the key, or {@code
     * list.size()} if there is no such element.
     */
    FIRST_AFTER {
      @Override
      public <E> int resultIndex(
          Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) {
        return LAST_PRESENT.resultIndex(comparator, key, list, foundIndex) + 1;
      }
    },
    
Return the index of the last list element that compares as less than the key, or -1 if there is no such element. 
/**
     * Return the index of the last list element that compares as less than the key, or {@code -1}
     * if there is no such element.
     */
    LAST_BEFORE {
      @Override
      public <E> int resultIndex(
          Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex) {
        return FIRST_PRESENT.resultIndex(comparator, key, list, foundIndex) - 1;
      }
    };

    abstract <E> int resultIndex(
        Comparator<? super E> comparator, E key, List<? extends E> list, int foundIndex);
  }

  
A specification for which index to return if the list contains no elements that compare as
equal to the key.

/**
   * A specification for which index to return if the list contains no elements that compare as
   * equal to the key.
   */ enum KeyAbsentBehavior {
    
Return the index of the next lower element in the list, or -1 if there is no such element. 
/**
     * Return the index of the next lower element in the list, or {@code -1} if there is no such
     * element.
     */
    NEXT_LOWER {
      @Override
      int resultIndex(int higherIndex) {
        return higherIndex - 1;
      }
    },
    
Return the index of the next higher element in the list, or list.size() if there is no such element. 
/**
     * Return the index of the next higher element in the list, or {@code list.size()} if there is
     * no such element.
     */
    NEXT_HIGHER {
      @Override
      public int resultIndex(int higherIndex) {
        return higherIndex;
      }
    },
    
Return ~insertionIndex, where insertionIndex is defined as the point at which the key would be inserted into the list: the index of the next higher element in the list, or list.size() if there is no such element. 
Note that the return value will be >= 0 if and only if there is an element of the list that compares as equal to the key. 
This is equivalent to the behavior of Collections.binarySearch(List<? extends Comparable<? super Object>>, Object) when the key isn't present, since ~insertionIndex is equal to -1 -
insertionIndex. 
/**
     * Return {@code ~insertionIndex}, where {@code insertionIndex} is defined as the point at which
     * the key would be inserted into the list: the index of the next higher element in the list, or
     * {@code list.size()} if there is no such element.
     *
     * <p>Note that the return value will be {@code >= 0} if and only if there is an element of the
     * list that compares as equal to the key.
     *
     * <p>This is equivalent to the behavior of {@link java.util.Collections#binarySearch(List,
     * Object)} when the key isn't present, since {@code ~insertionIndex} is equal to {@code -1 -
     * insertionIndex}.
     */
    INVERTED_INSERTION_INDEX {
      @Override
      public int resultIndex(int higherIndex) {
        return ~higherIndex;
      }
    };

    abstract int resultIndex(int higherIndex);
  }

  
Searches the specified naturally ordered list for the specified object using the binary search
algorithm.

Equivalent to binarySearch(List<Object>, Function<? super Object,Object>, Object, Comparator<? super Object>, KeyPresentBehavior, KeyAbsentBehavior) using Ordering.natural. 
/**
   * Searches the specified naturally ordered list for the specified object using the binary search
   * algorithm.
   *
   * <p>Equivalent to {@link #binarySearch(List, Function, Object, Comparator, KeyPresentBehavior,
   * KeyAbsentBehavior)} using {@link Ordering#natural}.
   */
  public static <E extends Comparable> int binarySearch(
      List<? extends E> list,
      E e,
      KeyPresentBehavior presentBehavior,
      KeyAbsentBehavior absentBehavior) {
    checkNotNull(e);
    return binarySearch(list, e, Ordering.natural(), presentBehavior, absentBehavior);
  }

  
Binary searches the list for the specified key, using the specified key function.

Equivalent to binarySearch(List<Object>, Function<? super Object,Object>, Object, Comparator<? super Object>, KeyPresentBehavior, KeyAbsentBehavior) using Ordering.natural. 
/**
   * Binary searches the list for the specified key, using the specified key function.
   *
   * <p>Equivalent to {@link #binarySearch(List, Function, Object, Comparator, KeyPresentBehavior,
   * KeyAbsentBehavior)} using {@link Ordering#natural}.
   */
  public static <E, K extends Comparable> int binarySearch(
      List<E> list,
      Function<? super E, K> keyFunction,
      @Nullable K key,
      KeyPresentBehavior presentBehavior,
      KeyAbsentBehavior absentBehavior) {
    return binarySearch(
        list, keyFunction, key, Ordering.natural(), presentBehavior, absentBehavior);
  }

  
Binary searches the list for the specified key, using the specified key function.

Equivalent to binarySearch(List<? extends Object>, Object, Comparator<? super Object>, KeyPresentBehavior, KeyAbsentBehavior) using Lists.transform(list,
keyFunction). 
/**
   * Binary searches the list for the specified key, using the specified key function.
   *
   * <p>Equivalent to {@link #binarySearch(List, Object, Comparator, KeyPresentBehavior,
   * KeyAbsentBehavior)} using {@link Lists#transform(List, Function) Lists.transform(list,
   * keyFunction)}.
   */
  public static <E, K> int binarySearch(
      List<E> list,
      Function<? super E, K> keyFunction,
      @Nullable K key,
      Comparator<? super K> keyComparator,
      KeyPresentBehavior presentBehavior,
      KeyAbsentBehavior absentBehavior) {
    return binarySearch(
        Lists.transform(list, keyFunction), key, keyComparator, presentBehavior, absentBehavior);
  }

  
Searches the specified list for the specified object using the binary search algorithm. The list must be sorted into ascending order according to the specified comparator (as by the Collections.sort(List, Comparator) method), prior to making this call. If it is not sorted, the results are undefined. 
If there are elements in the list which compare as equal to the key, the choice of KeyPresentBehavior decides which index is returned. If no elements compare as equal to the key, the choice of KeyAbsentBehavior decides which index is returned. 
This method runs in log(n) time on random-access lists, which offer near-constant-time
access to each list element.

Params:
  • list – the list to be searched.
  • key – the value to be searched for.
  • comparator – the comparator by which the list is ordered.
  • presentBehavior – the specification for what to do if at least one element of the list
    compares as equal to the key.
  • absentBehavior – the specification for what to do if no elements of the list compare as
    equal to the key.
Returns:the index determined by the KeyPresentBehavior, if the key is in the list; otherwise the index determined by the KeyAbsentBehavior.
/**
   * Searches the specified list for the specified object using the binary search algorithm. The
   * list must be sorted into ascending order according to the specified comparator (as by the
   * {@link Collections#sort(List, Comparator) Collections.sort(List, Comparator)} method), prior to
   * making this call. If it is not sorted, the results are undefined.
   *
   * <p>If there are elements in the list which compare as equal to the key, the choice of {@link
   * KeyPresentBehavior} decides which index is returned. If no elements compare as equal to the
   * key, the choice of {@link KeyAbsentBehavior} decides which index is returned.
   *
   * <p>This method runs in log(n) time on random-access lists, which offer near-constant-time
   * access to each list element.
   *
   * @param list the list to be searched.
   * @param key the value to be searched for.
   * @param comparator the comparator by which the list is ordered.
   * @param presentBehavior the specification for what to do if at least one element of the list
   *     compares as equal to the key.
   * @param absentBehavior the specification for what to do if no elements of the list compare as
   *     equal to the key.
   * @return the index determined by the {@code KeyPresentBehavior}, if the key is in the list;
   *     otherwise the index determined by the {@code KeyAbsentBehavior}.
   */
  public static <E> int binarySearch(
      List<? extends E> list,
      @Nullable E key,
      Comparator<? super E> comparator,
      KeyPresentBehavior presentBehavior,
      KeyAbsentBehavior absentBehavior) {
    checkNotNull(comparator);
    checkNotNull(list);
    checkNotNull(presentBehavior);
    checkNotNull(absentBehavior);
    if (!(list instanceof RandomAccess)) {
      list = Lists.newArrayList(list);
    }
    // TODO(lowasser): benchmark when it's best to do a linear search

    int lower = 0;
    int upper = list.size() - 1;

    while (lower <= upper) {
      int middle = (lower + upper) >>> 1;
      int c = comparator.compare(key, list.get(middle));
      if (c < 0) {
        upper = middle - 1;
      } else if (c > 0) {
        lower = middle + 1;
      } else {
        return lower
            + presentBehavior.resultIndex(
                comparator, key, list.subList(lower, upper + 1), middle - lower);
      }
    }
    return absentBehavior.resultIndex(lower);
  }
}