hangscer

scala写算法-二分查找

2017/06/13

昨天面试,考了二分查找,当时没写出来😢。
今天仔细想想还是蛮简单的,这里的算法采用递归查找:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def fun(array: Array[Int],left:Int,right:Int,target:Int):Option[Int]={
val mid=(left+right)/2
if(array(mid)==target)
return Some(mid)
if(array(mid)>target){
if(array(mid-1)<target)
return None
return fun(array,left,mid-1,target)
}
if(array(mid)<target){
if(array(mid+1)>target)
return None
return fun(array,mid+1,right,target)
}
if(left>=right)
return None
return None
}
val intArray=Array(1,3,5,7,9)
println(fun(intArray,0,intArray.length-1,3))//Some(1)
println(fun(intArray,0,intArray.length-1,7))//Some(3)
println(fun(intArray,0,intArray.length-1,4))//None
println(fun(intArray,0,intArray.length-1,6))//None