Is this binary search close to idiomatic OCaml?

let binsearch ~arr ~cmp x = (
    let cmpx = cmp x in
    (* Assuming arr is ordered according to cmp, then (bs min max) is an   *)
    (* index of a value v in arr such that ((cmp x value) = 0) between     *)
    (* min (inclusive) and max (exclusive).                                *)
    let rec bs min max =
      if min >= max then (
        None
      ) else (
        (* mid is always strictly less than max because min < max. *)
        let mid = (min + max) / 2 in
        let delta = (cmpx (Array.get arr mid))
        in (
          if delta = 0 then (
            Some mid
          ) else if delta < 0 then (
            (* since mid < max, we make progress *)
            bs min mid
          ) else (
            bs (mid + 1) max
          )))
    in bs 0 (Array.length arr));;

and then it can be used thus

let a = [|1; 2; 4; 4; 4; 7; 9; 9; 11; 16|];;

let bs = binsearch ~arr:a ~cmp:compare;;

let results = (bs 0, bs 1, bs 2, bs 3, bs 4, bs 5, bs 6, bs 7, bs 8,
               bs 9, bs 10, bs 11, bs 12, bs 13, bs 14, bs 15, bs 16, bs 17);;

 (results = (None, Some 0, Some 1, None, Some 2, None, None, Some 5, None,
             Some 7, None, Some 8, None, None, None, None, Some 9, None));;

Generally speaking, yes. I only have a couple of minor remarks.

let cmpx = cmp x in

Using partially-applied functions is actually slightly slower with the native-code compiler. The cmp function (like most functions) isn't going to do anything until it gets all its arguments, so cmpx under the hood is fun y => cmp x y. It's faster (not by much, but it can matter in an inner loop) if you write let delta = cmpx x (Array.get arr mid) below.

Speaking of which, arr.(mid) is exactly identical to (Array.get arr mid), but more usual. If you're going for speed, write Array.unsafe_get arr mid, which will save a few cycles, at the expense of putting the onus on you to verify that you are not making an array access out of bounds (here, it's easy to see that you are not).

You have many superfluous parentheses; they are a little surprising to a habitual Ocaml programmer. let … in … has lower precedence than anything else, and if … then … else … has lower precedence than arithmetic and function calls. This is how I'd write your function:

let binsearch ~arr ~cmp x =
  (* Assuming arr is ordered according to cmp, then [bs min max] is an   *)
  (* index of a value v in arr such that [(cmp x value) = 0] between     *)
  (* min (inclusive) and max (exclusive).                                *)
  let rec bs min max =
    if min >= max then
      None (* we are down to an empty slice of the array *)
    else
      (* mid is always strictly less than max because min < max. *)
      let mid = (min + max) / 2 in
      let delta = cmp x (Array.unsafe_get arr mid) in
      if delta = 0 then Some mid else
      if delta < 0
      then bs min mid
      else bs (mid + 1) max
  in bs 0 (Array.length arr);;

(Details of when to put newlines, especially relative to in, are matters of taste.)

StackExchange Code Review Q#11952, answer score: 3