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