Scala Binary Search

bin-search.scala

import scala.annotation.tailrec
object BinarySearchApp{

  def main(args: Array[String]){
    val l = List(1,2,4,5,6, 8,9,25,31);
    println("Hello World!")
    println(search2(5, l))
    println(search2(6, l))
    println(search2(7, l))
  }

  def search(target:Int, l:List[Int]) = {
    @tailrec 
    def recursion(low:Int, high:Int):Option[Int] = (low+high)/2 match{
      case _ if high < low => None 
      case mid if l(mid) > target => recursion(low, mid-1)      
      case mid if l(mid) < target => recursion(mid+1, high)
      case mid => Some(mid)
    } 
    recursion(0,l.size - 1)
  }

  def search2(target:Int, l:List[Int]) = {
    def recursion(mid:Int, list:List[Int]):Option[Int]=  list match {
      case tar::Nil if tar == target => Some(tar)
      case tar::Nil => None 
      case ls => {
          val(lows,highs) = ls.splitAt(mid) 
          if (ls(mid)>target) 
            recursion((lows.size)/2, lows)
          else 
            recursion((highs.size)/2, highs)
         }
    }

    recursion((l.size)/2, l);
  }
}

Hello, you might find this intresting to read http://googleresearch.blogspot.se/2006/06/extra-extra-read-all-about-it-nearly.html

u can avoid a serious bug by changing the code from (high +mid) / 2 to low + (high - low) / 2, this is safe from overflow.

the second one does not return an index of the target item, it returns the target which is not proper for the search function

The second one "search2" doesn't work as expected. It is missing a elseif clause

def binarySearch[T <% Ordered[T]](xs: List[T], elem: T): Option[T] = {

    def search(xs: List[T], mid: Int): Option[T] = xs match {
      case v :: Nil if v == elem => Some(v)
      case _ :: Nil => None
      case ls =>
        val (fh, sh) = xs.splitAt(mid)
        val midElem = ls(mid)
        if (midElem < elem) search(sh, sh.length / 2)
        else if (midElem > elem) search(fh, fh.length / 2)
        else Some(midElem)
    }

    search(xs, xs.length / 2)
  }