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)
  }
}