binary-search

[Brian Watkins]

There's a standard Java binarySearch method in java.util.Collections
(and also in java.util.Arrays, for all primitive arrays) that allows
one to search for the index of an item in a sorted collection (that
supports index access).

Running (. java.util.Collections (binarySearch coll key)) in Clojure
tends to produce errors on collections of sorted numerical values. It
turns out that BigInteger (a standard Clojure numeric type) doesn't
like to be compared to ordinary Integers in Java; in Clojure native
code it works just fine.

There should be a binary-search method in the Clojure standard library
tp avoid the lurking potential problem. Otherwise users are likely to
suffer from the worst kind of bug using java.util.Collections. The
code seems to work fine, even tests fine, until it hits the one data
set that needs promotion to BigInteger and then fails mysteriously and
intermittently.

Maybe something like this:
(defn binary-search
([coll key] (binary-search coll key 0 (count coll)))
([coll key first last] (let [mid (quot (+ first last) 2)
midval (get coll mid)]
(cond (= key midval) mid
(< key midval)
(binary-search coll key
first mid)
't (binary-search coll key
(inc mid)
last)))))

[Rich Hickey]

On Aug 2, 10:07 am, Brian Watkins <WildU...@gmail.com> wrote:
> There's a standard Java binarySearch method in java.util.Collections
> (and also in java.util.Arrays, for all primitive arrays) that allows
> one to search for the index of an item in a sorted collection (that
> supports index access).
>
> Running (. java.util.Collections (binarySearch coll key)) in Clojure
> tends to produce errors on collections of sorted numerical values. It
> turns out that BigInteger (a standard Clojure numeric type) doesn't
> like to be compared to ordinary Integers in Java; in Clojure native
> code it works just fine.
>
> There should be a binary-search method in the Clojure standard library
> tp avoid the lurking potential problem. Otherwise users are likely to
> suffer from the worst kind of bug using java.util.Collections. The
> code seems to work fine, even tests fine, until it hits the one data
> set that needs promotion to BigInteger and then fails mysteriously and
> intermittently.
>

I'm not sure the failure is mysterious, as the exception is pretty
clear, but the solution is easy once you know that Clojure's compare
function implements Comparator:

user=> (Collections/binarySearch [1 2 3] 2)
1

user=> (Collections/binarySearch [1 2M 3] 2)
java.lang.ClassCastException: java.lang.Integer cannot be cast to
java.math.BigDecimal
at java.math.BigDecimal.compareTo(BigDecimal.java:205)
at java.util.Collections.indexedBinarySearch(Collections.java:215)
at java.util.Collections.binarySearch(Collections.java:201)

;binarySearch can take a Comparator to use:
user=> (Collections/binarySearch [1 2M 3] 2 compare)
1

While I could provide a specific wrapper for this function, I think
people need to be generally aware that Clojure's numbers are of
heterogeneous types, and take care when interacting with any Java
methods that presume homogenous types, e.g. when hashing or comparing.

Rich