bisectRight.scala

import scala.annotation.tailrec

object bisect {
    
  /**
  * Port of Python's bisect_right implemented using tail recursion.
  *
  * Return the index where to insert item x in Array A, assuming A is sorted.
  * The return value is such that all e in a[:i] have e <= x, and all e in
  * a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
  * insert just after the rightmost x already there.
  * Optional args lo (default 0) and hi (default len(a)) bound the
  * slice of a to be searched.
  */
  def bisectRight(A: Array[Int], x: Int): Int =
    bisectRight(A, x, 0, A.length)

  @tailrec
  private def bisectRight(A: Array[Int],
                          x: Int,
                          lo: Int,
                          hi: Int): Int = {  
      
      if (lo < hi) {
          val mid: Int = (lo + hi) / 2
          if (x < A(mid)) {
            bisectRight(A, x, lo, mid)
          } else {
            bisectRight(A, x, mid + 1, hi)
          }   
      } else lo
      
  }
}