iterative binary search implementation in f#

binary-search, f#

Solution

Use a recursive function:

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)

Non-recursive version (adapted from Gene's answer):

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

But I think that the recursive version is preferable: more idiomatic, as efficient as the iterative one because it uses tail calls.

Problem

I am trying to write a binary search in f#, but stumbled at a problem: ``` 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 ``` It is giving error at the line which says `true` saying it expected an expression of type `unit()` instead got `bool`. What is the correct way to write this function? Edit: Temporarily I took to writing as follows: ``` 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 ``` But execution wise I think I am doing a lot of operations here than intended...

Original source