functional-programming - 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) ;;

我正在尝试在 OCaml 中进行二进制搜索。这段代码有什么问题？它总是返回-1。它是一个字符串数组，因此比较元素会给出值 0、-1 或 1，如果它们相等，则第一个元素较小和第一个元素分别较大（文档说正整数和负整数，但我已经在解释器中测试并收到 1 和 -1 ）。关于我在这里犯的错误的任何提示？

Answer 1

将此更改if (String.compare arr.(mid) word = 1) 为-1.

String.compare1如果左侧大于右侧则返回。

注意：所采用的一般方法包含此处维基百科文章中描述的已知小错误： https ://en.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues

基本上，计算midas(min + max) / 2会为足够大的数字提供整数溢出。