public int binarysearch(int value) {
    int sz = size;

    if (!sorted) {
      // Linear search.
      for (int i = 0; i < sz; i++) {
        if (values[i] == value) {
          return i;
        }
      }

      return -sz;
    }

    /*
     * Binary search. This variant does only one value comparison
     * per iteration but does one more iteration on average than
     * the variant that includes a value equality check per
     * iteration.
     */

    int min = -1;
    int max = sz;

    while (max > (min + 1)) {
      /*
       * The guessIdx calculation is equivalent to ((min + max)
       * / 2) but won't go wonky when min and max are close to
       * Integer.MAX_VALUE.
       */
      int guessIdx = min + ((max - min) >> 1);
      int guess = values[guessIdx];

      if (value <= guess) {
        max = guessIdx;
      } else {
        min = guessIdx;
      }
    }

    if ((max != sz)) {
      return (value == values[max]) ? max : (-max - 1);
    } else {
      return -sz - 1;
    }
  }
Performs a binary search on a sorted list, returning the index of the given value if it is
present or {@code (-(insertion point) - 1)} if the value is not present. If the list is not
sorted, then reverts to linear search and returns {@code -size()} if the element is not found.

@param value value to find
@return index of value or {@code (-(insertion point) - 1)} if the value is not present
android/android_framework/dex-maker/src/main/java/com/android/dx/util/IntList.java