# 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 inif 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() |> ignore0 // 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)

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