I decided to implement linear search before going after binary search. Now, I’m ready!

With linear search, we required the elements be sorted. We didn’t require the elements be bounded. In binary search, the inputs must be bounded because we maintain two indexes or pointers that start at the beginning and end of the search space. Because we move one index half-way closer to the other each iteration, the time complexity is O(log n).

Solution

Loop recur was a nice combination for linear search. So, we’ll use it again here.

(defn binary-search
  [x xs]
  (loop [low 0
         high (dec (count xs))]
    (when (<= low high)
      (let [mid (quot (+ low high) 2)
            mid-val (xs mid)]
        (cond
          (= x mid-val) mid
          (< x mid-val) (recur low (dec mid))  ;; x in left half, scoot high index
          :else         (recur (inc mid) high) ;; x in right half, scoot low index
          )))))

Challenges

Two Are Better Than One

One of the hardest parts for me in figuring this out was that I forgot two indexes are necessary. I tried using a single index and it never converged.

Integer Division

In addition, my mid formula was wrong!

(let [low 1
      high 10]
  [(/ (+ low high) 2)      ;; 11/2
   (quot (+ low high) 2)]) ;; 5

Sometimes, / returns a clojure.lang.Ratio while quot always returns a java.lang.Long. I’ve never used quot before. In C, / truncates toward 0 when both inputs are ints, which is what we need.

Tests

(are [x xs i] (= (binary-search x xs) i)
  1 [] nil
  1 [1] 0
  1 [1 3] 0
  -1 [1 3 5 7 9] nil
  1 [1 3 5 7 9] 0
  3 [1 3 5 7 9] 1
  5 [1 3 5 7 9] 2
  7 [1 3 5 7 9] 3
  9 [1 3 5 7 9] 4
  10 [1 3 5 7 9] nil
  25 (vec (range 101)) 25
  75 (vec (range 101)) 75)