Binary search inside sorted array in OCaml

Question

let find arr word =
  let rec binaryserach arr word min max =
    let mid = (min + max) / 2 in
    if max < min then -1 else
    if (String.compare arr.(mid)  word = 0) then mid else 
    if (String.compare arr.(mid)  word = 1) then (binaryserach arr word (mid+1) max) else
      binaryserach arr word min (mid-1) in 
  binaryserach arr word 0 ((Array.length arr) - 1) ;;

I am trying to do binary serach in OCaml. What is wrong in this code? It always return -1. It is an array of strings so that comparing elements gives values 0,-1 or 1 if they are equal, first element lesser and first element greater respectively(Documentation says positive and negative integers but I have tested in interpreter and recieved 1 and -1). Any hint about the mistake I have made here?

Answer 1

Change this if (String.compare arr.(mid) word = 1) to -1.

String.compare returns 1 if left side is greater than right.

Note: the general approach taken contains minor known error described in wikipedia article here: https://en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues

Basically, calculating mid as (min + max) / 2 gives an integer overflow for large enough numbers.