gistfile1.scala

  /**
   * This is a binary search operation
   * if the element is found, and it matches an element at an index precisely,
   * then that index is returned.
   *
   * If the element is not found it will return a negative number.
   * the index returned is as follows, if it is before the 0th index
   * then -1 is returned
   * if it is before the first index, but after the zeroeth
   * then -2 is returned
   * if it is before the second index, but after the first
   * then -3 is returned
   * and so on.
   * if it is after the last index
   * then -(size+1) is returned (as would be expected).
   *
   * Here are some examples
   * xs = [3,5,7,9]
   * Here is a break down of the locations
   * for each input of bs(xs, x)
   * where x is one of:
   * [-Inf,3) = -1
   * [3,3]    = 0
   * (3,5)    = -2
   * [5,5]    = 1
   * (5, 7)   = -3
   * [7,7]    = 2
   * (7,9)    = -4
   * [9,9]    = 3
   * (9, Inf] = -5
   */
  def bs[A: Ordering](a: Seq[A], i: A): Int = {
    val o = implicitly[Ordering[A]]
    var low: Int = 0
    var high: Int = a.size - 1
    while (low <= high) {
      val mid: Int = (low + high) >>> 1
      val midVal: A = a(mid)
      if (o.lt(midVal, i)) low = mid + 1
      else if (o.gt(midVal, i)) high = mid - 1
      else {
        //now since we are allowing duplicates in the arrays
        //and we want to return consistent results
        //we are going to back scan, and keep going until we hit the start
        //of a run, for example on an array of [1,2,5,5,6]
        //This ensures that a search for 5 will always yield
        //index 2 and never index 3 (no matter how many 5's are in there
        //index 2 will be returned, the array still must be sorted
        //for this to work correctly obviously
        var prevIdx = mid - 1
        while (prevIdx >= 0) {
          val prevVal = a(prevIdx)
          if (o.equiv(prevVal, i)) prevIdx -= 1
          else return (prevIdx + 1)
        }
        return 0
      }
    }
    return -(low + 1)
  }