iterative binary search implementation in f#

Question

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...

Answer 1

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.