# Binary Search Of Sorted Array In Clojure Basic Algorithms Part Three

## Aug 3, 2016 09:03 · 580 words · 3 minute read clojure development algorithms

### The problem

Find an element in a sorted array using binary search

### The solution

The solution is pretty straight forward. I added in some printlns to get a sense of how we drill down in the recursion to find the element.

``````(defn binary-search [v value]
(loop [low 0 high (dec (count v))
depth 0]
(let [half-way (quot (+ high low)  2)]
(do (println (str "half-way is " half-way))
(println (str "low is " low))
(println (str "high is " high))
(println (str "depth is " depth))
(if (<= high (inc low))
(cond (= value (v low)) low
(= value (v high)) high
:else nil)
(let [middle (quot (+ low high) 2)]
(if (< (v middle) value)
(recur (inc middle) high (inc depth))
(recur low middle (inc depth)))))))))
``````

You can call the function like this:

``````(binary-search (vec (range 0 10)) 1000)
``````

Dialing up the range you can see how many steps it takes to get to the value.

There’s also a java implementation of binary search.

``````java.util.Collections.binarySearch(List<T> list, T key, Comparator<? super T> c).
``````

I decided to see compare the two implementations with a variety of elements in the collection while, looking for a random element. I took the average time over 100,000 runs to see how different the two implementations did.

The two implementations that I ran were.

``````(defn binary-search [v value]
(loop [low 0 high (dec (count v))
depth 0]
(let [half-way (quot (+ high low)  2)]
(if (<= high (inc low))
(cond  (= value (v low)) low
(= value (v high)) high
:else nil)
(let [middle (quot (+ low high) 2)]
(if (< (v middle) value)
(recur (inc middle) high (inc depth))
(recur low middle (inc depth))))))))
``````

vs

``````(defn java-binary-search [v value]
(Collections/binarySearch v value compare))
``````

For 1000000 elements in the array using java-binary-search I got.

``````{:average 30.04732094221115, :std-deviation 9.367210018023908}
``````

For 1000000 element in the array using binary-search I got.

``````{:average 29.451808820724487, :std-deviation 9.199826118870515}
``````

Insanely they were basically the same. It took about 5 mins to get the results back for 10,000 runs. So I decided to dial up the number of elements to 10,000,000 and reduce the number of runs to 100.

For java-binary-search I got

``````{:average 870.9942288208008, :std-deviation 705.2356880437546}
``````

For binary-search I got

``````{:average 728.1910227966308, :std-deviation 441.7981992776274}
``````

There is some difference here. The standard deviations show that java-binary-search has a slightly wider spread, which means it could be faster in some cases with some outliers as compared to binary search. Since I didn’t I decided to look at the implementation of binarySearch within Java itself. For the record here it is.

``````private static <T> int indexedBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) {
int low = 0;
int high = l.size()-1;
while (low <= high) {
int mid = (low + high) >>> 1;
T midVal = l.get(mid);
int cmp = c.compare(midVal, key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}