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

但是在执行方面，我认为我正在进行比预期更多的操作...

- deostroll

---

它不起作用：请看我对Gene答案的评论。 - MiMo

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

但是我认为递归版本更好：更符合习惯，因为它使用尾调用而且和迭代版本一样高效。

- MiMo

---

为什么？由于这个实现是一个尾调用，所以你不会遇到堆栈溢出的问题。这是一个非常适合 F# 递归的例子。 - vcsjones

因为“递归是FP的goto语句”，而且“初学者的代码也是好的”。我知道这听起来有点过于热情了，但其中确实有一些真理... - nicolas

Answer 2

首先，如果value大于最右边的words元素（例如使用find [|"a";"b";"c";"d"|] "e"进行简单测试），您的算法将不会终止。

纠正这个问题并加入一些小的优化后，最终的交互式实现可能不会比下面更短

let find (words: string[]) (value:string) =
  let mutable lpos = words.Length - 1
  if value.CompareTo(words.[lpos]) > 0 then
    false
  else
    let mutable mid = 0
    let mutable fpos = 0
    let mutable cont = true
    while fpos < lpos && cont do
      mid <- (fpos + lpos) / 2
      match sign(value.CompareTo(words.[mid])) with
      | -1 -> lpos <- mid
      | 1 -> fpos <- mid
      | _ -> cont <- false
  not cont

更新： 这就是匆忙回答且周围没有电脑时的结果 :(. 上面被删除的内容不值得骄傲。由于MiMo已经解决了上面代码段中的所有问题，我将尝试不同的方法来证明自己，即尝试演示MiMo的递归实现在尾调用消除后如何几乎文字转换为他的非递归实现。

我们将分两步进行：首先使用带标签和跳转的伪代码来说明编译器如何消除这种形式的尾递归，然后将伪代码转换回F#以获取命令式版本。

// Step 1 - pseudo-code with tail recursion substituted by goto
let find(words:string[]) (value:string) =
    let mutable fpos = 0
    let mutable lpos = words.Length - 1
    findRec:
        match fpos - lpos > 0 with
        | true -> return false
        | _ -> let mid = (fpos + lpos) / 2
               match sign(value.CompareTo(words.[mid])) with
               | -1 -> lpos <- mid - 1
                       goto findRec
               | 1 ->  fpos <- mid + 1
                       goto findRec
               | _ -> return true

现在，由于缺少goto，我们需要想出一种等效的构造方式，同时保持在合法的F#构造集内。最简单的方法是使用while...do结构与可同时信号while何时停止和携带返回值的可变state变量。两个布尔值的元组就足够了：

// Step 2 - conversion of pseudo-code back to F#
let find(words:string[]) (value:string) =
    let mutable fpos = 0
    let mutable lpos = words.Length - 1
    let mutable state = (true,false)
    while (fst state) do
        match fpos - lpos > 0 with
        | true -> state <- (false,false)
        | _ -> let mid = (fpos + lpos) / 2
               match sign(value.CompareTo(words.[mid])) with
               | -1 -> lpos <- mid - 1
               | 1 -> fpos <- mid + 1
               | _ -> state <- (false,true)
    snd state

总结一下，“a-la编译器优化”的递归版本和手动挑选的命令式版本之间的差异微不足道，这应该表明，在性能方面正确排列的递归版本与命令式版本是等效的。但是，由于编译器执行的转换，它不留下有状态编码的错误空间。

- Gene Belitski

---

如果 words 只包含一个项目，则它无法工作（循环立即退出）。 - MiMo

如果value等于words的最后一项，它也会进入无限循环。 - MiMo

@MiMo：感谢您指出更多的问题；在没有重新检查原始实现之前不应该匆忙回复 :(. - Gene Belitski

Answer 3

我建议使用递归解决方案，如下所示：

let find (xs: _ []) x =
  let rec loop i0 i2 =
    match i2-i0 with
    | 0 -> false
    | 1 -> xs.[i0]=x
    | di ->
        let i1 = i0 + di/2
        let c = compare x xs.[i1]
        if c<0 then loop i0 i1
        else c=0 || loop i1 i2
  loop 0 xs.Length

F# 将尾调用转换为跳转指令：

internal static bool loop@4<a>(a[] xs, a x, int i0, int i2)
{
    a a;
    while (true)
    {
        int num = i2 - i0;
        switch (num)
        {
        case 0:
            return false;
        case 1:
            goto IL_50;
        default:
        {
            int i3 = i0 + num / 2;
            a = xs[i3];
            int c = LanguagePrimitives.HashCompare.GenericComparisonIntrinsic<a>(x, a);
            if (c < 0)
            {
                a[] arg_37_0 = xs;
                a arg_35_0 = x;
                int arg_33_0 = i0;
                i2 = i3;
                i0 = arg_33_0;
                x = arg_35_0;
                xs = arg_37_0;
            }
            else
            {
                if (c == 0)
                {
                    return true;
                }
                a[] arg_4A_0 = xs;
                a arg_48_0 = x;
                int arg_46_0 = i3;
                i2 = i2;
                i0 = arg_46_0;
                x = arg_48_0;
                xs = arg_4A_0;
            }
            break;
        }
        }
    }
    return true;
    IL_50:
    a = xs[i0];
    return LanguagePrimitives.HashCompare.GenericEqualityIntrinsic<a>(a, x);
}

public static bool find<a>(a[] xs, a x)
{
    return File1.loop@4<a>(xs, x, 0, xs.Length);
}

- J D