Linear Search in Clojure

I consider myself a classically trained computer scientist. However, I don’t regularly practice implementing algorithms at home. I hope to do more of that! At work, I do much higher level things, like partnering with a product manager, establishing and maintaining monitoring and alerting, setting up on-call rotations, capacity planning, etc. However, I wanted to see if I could implement a binary search algorithm. Then I thought, can I do a linear search?

First, what do I mean by search? Find the location, or index, of a desired item in a sorted collection.

We’ll assume the collection is sorted in ascending order (1, 2, 3, … and not 10, 9, 8, …). This doesn’t actually matter for linear search. It does matter for binary search! The best case for a linear search algorithm is O(1), when the desired item is the first in the collection. The worst case is O(n), when the desired item is the last in the collection or isn’t present at all. One thing I really want in my implementation is early return.

Since most of my algorithmic training was done in C (probably C89 since variable declarations for iterators had to happen outside of for loops), I thought I’d start with while. This turned out to be very painful! I included a little test suite.

(ns sorting
  (:require [clojure.test :refer [are]]))

(defn linear-search-while
  [x xs]
  (let [i (atom 0)]
    (while
     (and (not= x (get xs @i))     ;; haven't found it yet
          (< @i (dec (count xs)))) ;; haven't gotten to the end yet
      (swap! i inc))
    (if (= x (get xs @i))          ;; find it?
      @i
      nil)))

(are [x xs i] (= (linear-search-while x xs) i)
  1 [] nil
  1 [1] 0
  1 [1 3 5 7 9] 0
  5 [1 3 5 7 9] 2
  9 [1 3 5 7 9] 4
  -1 [1 3 5 7 9] nil)

I got the stopping condition in the while loop wrong several times. First, we want to stop when we’ve found x. Second, we want to stop once we’ve exhausted the collection. I can’t think of a time I had less fun writing Clojure. Mutation, manually keeping track of an index, fiddling with a while loop. This is the worst. It does work, though! One thing that jumped out to me implementing this the use of nil instead of a sentinel value, like -1, that is common when coding in something like C.

What’s like a while loop but way better? Loop and recur! With a while loop, you say what must be true to continue. With loop recur, you say when to try another iteration and with what input. So, here’s a version that uses that.

(defn linear-search-loop-recur-cond
  [x xs]
  (loop [i 0]
    (cond
      (>= i (count xs)) nil    ;; we're at the end, not found
      (= x (nth xs i)) i       ;; found it
      :else (recur (inc i))))) ;; try again at the next spot

This is so much better!

Here’s another way to do it.

(defn linear-search-loop-recur-when
  [x xs]
  (loop [i 0]
    (when (< i (count xs))  ;; don't run off the end
      (if (= x (nth xs i))  ;; find it?
        i                   ;; found it
        (recur (inc i)))))) ;; try again at the next spot

It’s the same number of lines. I like both.