f#中的迭代二进制搜索实现

Question

我试图在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

但执行明智我认为我在这里做了很多操作而不是预期......

Answer 1

使用递归函数:

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

但我认为递归版本更可取:更具惯用性,与迭代版本一样高效,因为它使用尾调用.