我试图在f#中编写二进制搜索,但偶然发现了一个问题:
let find(words:string[]) (value:string) = let mutable mid = 0 let mutable fpos = 0 let mutable lpos = words.Length - 1 while fpos < lpos do mid <- (fpos + lpos) / 2 if value < words.[mid] then lpos <- mid else if value > words.[mid] then fpos <- mid else if value = words.[mid] then true false
它在线上给出错误true
说它预期类型的表达式unit()
得到了bool
.编写此函数的正确方法是什么?
编辑:
我暂时写了如下:
let find(words:string[]) (value:string) = let mutable mid = 0 let mutable fpos = 0 let mutable lpos = words.Length - 1 let ret = false while fpos < lpos && ret = false do mid <- (fpos + lpos) / 2 if value < words.[mid] then lpos <- mid else if value > words.[mid] then fpos <- mid else if value = words.[mid] then ret <- true ret
但执行明智我认为我在这里做了很多操作而不是预期......
使用递归函数:
let find(words:string[]) (value:string) = let rec findRec fpos lpos = if fpos > lpos then false else let mid = (fpos + lpos) / 2 if value < words.[mid] then findRec fpos (mid-1) else if value > words.[mid] then findRec (mid+1) lpos else true findRec 0 (words.Length-1)
非递归版本(改编自Gene的答案):
let find (words: string[]) (value:string) = let mutable mid = 0 let mutable fpos = 0 let mutable lpos = words.Length - 1 let mutable cont = true while fpos <= lpos && cont do mid <- (fpos + lpos) / 2 match sign(value.CompareTo(words.[mid])) with | -1 -> lpos <- mid-1 | 1 -> fpos <- mid+1 | _ -> cont <- false not cont
但我认为递归版本更可取:更具惯用性,与迭代版本一样高效,因为它使用尾调用.