Tuesday, April 20, 2010

The "binary search" script

For some reason, it could not get pasted there.

import util.Random
val toFind = args(0).toInt
val r = new Random()
val a = (for (i<- 1 to 100) yield r.nextInt(100)).toList.sort(_<_).toArray
def binsearch(x:Int, a:Array[Int],first:Int, last:Int):Int = {
    if (last-first<=1) {
        if (a(first)==x) return first
        else if (a(last)==x) return last
        else return -1} else {
            val mid = (last+first)/2
            if (a(mid)>=x) return binsearch(x, a, first, mid)
                else return binsearch(x, a, mid, last)
for (el<-0 to 99) println(el+":"+a(el))
val res = binsearch(toFind, a, 0,99)
println ("res="+res)

No comments:

Post a Comment