Skewed binary search taking time O(lg i), where i is the index found

search.scala

/*
 * Returns the smallest index, i, into sizes such that `vs(i) >= n`,
 * assuming `vs` is sorted. If `n` exceeds the maximum value in `vs`,
 * throws an exception. This takes time `O(lg i)`, so searches which
 * succeed near the front of `vs` return more quickly.
 */
def search(vs: Vector[Long], n: Long): Int = {

  // progressively double index, starting from 0, until
  // hitting an index whose value exceeds `n`, then use
  // the remaining range for a binary search
  @annotation.tailrec
  def doublingSearch(prev: Int, current: Int): Int =
    if (current > vs.size || vs(current - 1) >= n)
      binarySearch(prev - 1, math.min(current, vs.size) - 1)
    else
      doublingSearch(current, current * 2)

  @annotation.tailrec
  def binarySearch(low: Int, high: Int): Int =
    if (low <= high) {
      val mid = (low + high) >>> 1
      val v = vs(mid)
      if (v < n) binarySearch(mid+1, high)
      else if (v > n) binarySearch(low, mid-1)
      else mid
    }
    else if (low >= vs.size)
      throw new IllegalArgumentException(s"value $n greater than max ${vs.lastOption.getOrElse(0)}")
    else low

  doublingSearch(1, 1)
}