BinarySearch

object first {
  def main(args: Array[String]): Unit = {
    println( binarySearch(Array(1,2,3,4), 3) )
  }

  def binarySearch(xs: Array[Int], x: Int): Int = {
    def bin(low: Int, high: Int): Int = {
        if (low == high) return -1

        val mid = (high + low) / 2
        if (xs(mid) == x) return mid

        else if (x > xs(mid)) {
            bin(mid+1, xs.length)
        } else {
            bin(0, mid)
        }
    }
    return bin(0, xs.length)
  }
}