3
\$\begingroup\$
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));;
\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ Thanks. I'm a little leery of dropping parentheses since I'm learning the language and haven't wrapped my head around the operator precedence yet. The abbreviated member access is a good point though, and thanks for the performance tips on partial evaluation. Your style of one keyword at the beginning of each line and one at the end makes things flow nicely. \$\endgroup\$ May 21, 2012 at 22:52
  • \$\begingroup\$ the let cmpx = cmp x in is a bad idea not only because it is not good for performance but also because you use this function only once and it is never a good idea to declare a function to use it only once. \$\endgroup\$
    – Thomash
    Jun 4, 2012 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.