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

Answer 1

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

String.compare returns 1 如果左侧大于右侧。

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

基本上，将 mid 计算为 (min + max) / 2 会给出足够大的整数溢出。

OCaml中排序数组内的二进制搜索

Binary search inside sorted array in OCaml

ocaml

functional-programming

ocaml-batteries