问题描述:

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 `if`

s 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)

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)
```