binary search

(* Using the binary search algorithm, an element can be found very quickly in a sorted array.
Write a function find : string array -> string -> int such that find arr word is the index of the word in the sorted array arr if it occurs in arr or -1 if word does not occur in arr.

The number or array accesses will be counted, to check that you obtain the expected algorithmic complexity. Beware that you really perform the minimal number of accesses. For instance, if your function has to test the contents of a cell twice, be sure to put the result of the access in a variable, and then perform the tests on that variable. *)

let find (arr: string array) (word: string) : int =
  let l = 0 in
  let r = Array.length(arr) - 1 in
  let rec bin (left: int) (right: int) : int =
    let middle = (left + right) / 2 in
    let mid_val = arr.(middle) in
    if left > right then -1
    else if mid_val = word then middle
    else if word > mid_val
    then
      bin (middle + 1) right
    else
      bin left (middle - 1)
  in bin l r
;;