Двоичный поиск внутри сортированного массива в 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) ;; 

Я пытаюсь сделать двоичный serach в OCaml. Что не так в этом коде? Он всегда возвращает -1. Это массив строк, так что сравнение элементов дает значения 0, -1 или 1, если они равны, первый элемент меньше и первый элемент больше соответственно (в документации указаны положительные и отрицательные целые числа, но я тестировал в интерпретаторе и получал 1 и -1). Любой намек на ошибку, которую я здесь сделал?

Answer 1

Изменить if (String.compare arr.(mid) word = 1) на -1.

String.compare возвращает 1, если левая сторона больше права.

Примечание: общий подход содержит незначительную известную ошибку, описанную в википедии статье здесь: https://en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues

В принципе, расчет mid в (min + max)/2 дает целочисленное переполнение для достаточно больших чисел.