当前位置: 动力学知识库 > 问答 > 编程问答 >

functional programming - F# BinarySearch return position

问题描述:

I'm trying to implement a simple binary search in F# as a way of learning functional programming. I've already implemented it in an imperative way in C# which is my main language, but I thought it would be a nice challenge and a good way to learn functional concepts by implementing it in a recursive sense in F#. I've gotten far enough that it properly finds the value, my problem is that I want the function to return -1 if the value is not in the array, and the index of the value otherwise, but I can't come up with a good way of keeping track of the index. Here's my code:

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

Since I split the list every iteration, I will get different indices when I move "up" into the array. In my example, the code returns 3 instead of 10.

What's the recommended way of fixing this? Any way to solve it is appreciated, though I would obviously prefer "correct" ways of doing it in a functional sense, since that's what I'm practicing. I would also like any advice concerning if my solution is bad from a performance point of view (for example, is it a bad idea to split the arrays in the first place?)

网友答案:

I would stick more with the original without copying the array (and use Option instead of the magic number -1 for failures):

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)

maybe you don't like all these ifs but still this is the obvious translation of the algorithm. And it does not mutate or reallocate anything.

If you want to remove the ifs you can do this:

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)

even more readable (but a bit boilerplatey):

[<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 please note that the last case is really a match all case I should probably write as | _ -> Some mid but I think in this case I may cheat for readabilities sake)

Performancewise the only thing you could improve is removing the recursion (but that should not be a problem if you enable optimization)

remark

as @kvb rightly noted (a+b)/2 is a bit of a risk (and I make this mistake regualary) - so if you have really big arrays and want to be safe better use this instead:

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

which is of course mathematically the same but for finite ranges and with overflow quite a difference

网友答案:

A slight variation, that doesn't require an "impossible" case:

let binarySearch value (array: 'T[]) =
    let rec loop lo hi =
        if lo <= hi then
            let mid = lo + ((hi - lo) >>> 1)
            match array.[mid] with
            | x when x = value -> Some mid
            | x when x < value -> loop (mid + 1) hi
            | _ -> loop lo (mid - 1)
        else None
    loop 0 (array.Length - 1)
分享给朋友:
您可能感兴趣的文章:
随机阅读: