F# BinarySearch 返回位置

标签 f# functional-programming binary-search

我正在尝试在 F# 中实现一个简单的二进制搜索,作为学习函数式编程的一种方式。我已经在我的主要语言 C# 中以命令式方式实现了它,但我认为通过在 F# 中以递归方式实现它,这将是一个很好的挑战,也是学习函数式概念的好方法。我已经走得够远了,它可以正确地找到值,我的问题是,如果值不在数组中,我希望函数返回 -1,否则返回值的索引,但我想不出来跟踪索引的好方法。这是我的代码:

let rec chop i (nums:array<int>) =
match nums with
| [||] -> -1
| [|x|] -> if x = i then x else -1
| _ -> 
    let mid = nums.Length / 2 in
    if nums.[mid] < i then (chop i nums.[mid..])
    elif nums.[mid] > i then (chop i nums.[..mid])
    else mid

[<EntryPoint>]
let main argv = 
    printfn "%d" (chop 20 (Array.init 100 (fun index -> index * 2)))
    System.Console.ReadKey() |> ignore
    0 // return an integer exit code

由于我每次迭代都会拆分列表,所以当我“向上”移动到数组中时,我会得到不同的索引。在我的示例中,代码返回 3 而不是 10。

推荐的解决方法是什么?任何解决它的方法都值得赞赏,尽管我显然更喜欢在功能意义上这样做的“正确”方法,因为这就是我正在练习的方法。我还想得到任何关于我的解决方案从性能角度来看是否糟糕的建议(例如,首先拆分数组是不是一个坏主意?)

最佳答案

我会更多地使用原件而不复制数组(并使用 Option 而不是魔数(Magic Number) -1 来表示失败):

let chop i (nums : int[]) =
    let rec find a b =
        if b < a then None else
        let mid = (a+b)/2
        let midValue = nums.[mid]
        if midValue = i then 
            Some mid 
        elif i < midValue then
            find a (mid-1)
        else
            find (mid+1) b
    find 0 (nums.Length-1)

也许您不喜欢所有这些if,但这仍然是算法的明显翻译。而且它不会改变或重新分配任何东西。

如果你想删除 ifs 你可以这样做:

let chop i (nums : int[]) =
    let rec find a b =
        if b < a then None else
        let mid = (a+b)/2
        match (compare i nums.[mid]) with
        | 0  -> Some mid
        | -1 -> find a (mid-1)
        | 1  -> find (mid+1) b
        | _  -> failwith "should never happen"
    find 0 (nums.Length-1)

更具可读性(但有点样板化):

[<Literal>] 
let Lt = -1
[<Literal>] 
let Gt = +1


let chop i (nums : int[]) =
    let rec find a b =
        if b < a then None else
        let mid = (a+b)/2
        match (compare i nums.[mid]) with
        | Lt -> find a (mid-1)
        | Gt -> find (mid+1) b
        | Eq -> Some mid
    find 0 (nums.Length-1)

(remark 请注意,最后一种情况实际上是所有情况的匹配,我可能应该写成 | _ -> Some mid 但我认为在这种情况下我可能为了可读性而作弊)

就性能而言,您唯一可以改进的是删除递归(但如果启用优化,这应该不是问题)

备注

正如@kvb 正确指出的那样,(a+b)/2 有点冒险(我经常犯这个错误)——所以如果你有非常大的阵列并且想要更安全改用这个:

let mid = a + (b - a) / 2

这当然在数学上是相同的,但对于有限范围和溢出有很大的不同

关于F# BinarySearch 返回位置,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25922027/

相关文章:

f# - 使用 TPL 的代码是否有更符合 F# 习惯的方式?

f# - 如何返回多个值并将它们分配给可变变量?

clojure - 什么时候在 Clojure 宏中使用 ~'some-symbol?

haskell - Monad 转换器库 - 使用哪一个?

algorithm - 解决 ACM TJU 2886 - 餐厅

c++ - 如何在二维数组中使用二进制搜索?

f# - 如何对 2 条记录的字段进行模式匹配?

c# - F# 类型到 Json 正在输出 Name@ 和 Name

typescript - 来自 fp-ts 和 URI 的 typescript 中更高种类的类型

java - 为什么二分查找返回-1