Binary search in Clojure

Binary search is an algorithm for finding a target item in a sorted list. As it’s quite a simple algorithm, it makes a nice example for introducing a few features in Clojure.

First, a review of the algorithm. If you haven’t encountered binary search before, it’s a good idea to try it out yourself on paper using a sorted list with around 10 elements in it.

The input to the algorithm is a sorted list which we’ll call numlist (for simplicity, we’ll assume the list contains integers, but the algorithm generalizes easily to any type of data provided methods of ordering the data and testing for equality exist), and a target to be searched for. Then:

  1. Set lower to 0 and upper to (length of list – 1). (Lists, like arrays, are assumed to be indexed from 0.)
  2. Test if lower > upper. If so, target is not found, so return nil.
  3. Calculate mid = (lower + upper)/2 (using integer division).
  4. Find the data stored at location mid and call it midvalue.
  5. If midvalue > target then if target is in the list, it’s in the portion of the list below mid so set upper to mid – 1 and repeat from step 2.
  6. If midvalue < target then if target is in the list, it’s in the portion above mid so set lower to mid + 1 and repeat from step 2.
  7. If midvalue == target, then target has been found, so return mid as the location of target in the list.

The algorithm is naturally recursive, in that each time target isn’t found, the list gets chopped in half (or as near to half as integer division will allow) and the search continues in the truncated portion of the list. It is this halving process that makes binary search an efficient algorithm, with logarithmic behaviour. For a list of length 2^n, it will take at most n comparisons to either find target or prove it’s not present.

The Clojure code looks like this:

(defn binsearch [numlist target]
  (def uppercount (dec (count numlist)))
  (loop [lower 0
        upper uppercount]
    (if (> lower upper) nil
      (let [mid (quot (+ lower upper) 2)
            midvalue (nth numlist mid)]
        (cond
          (> midvalue target) (recur lower (dec mid))
          (< midvalue target) (recur (inc mid) upper)
          (= midvalue target) mid)))))

We’ll step through the code to explain the various features. On line 1, the function binsearch is defined, and it takes two arguments: numlist and target. numlist is a list rather than a single number, while target is a bare number. After loading the function into the REPL, it can be called with a line like

(binsearch '(1 3 4 5 6 7 8) 5)

Note that when giving a list as an argument to a function, you must prefix it with a single quote. This tells the REPL that the list is to be treated as a list of data, and not as a function. If you omit the quote, you’ll get an error stating that ‘1’ (the first element in the list) can’t be defined as a function (the actual error message is #<CompilerException java.lang.ClassCastException: java.lang.Integer cannot be cast to clojure.lang.IFn but that’s what it’s saying).

The output from the above call is just 3, since the target of 5 is found at location 3 in numlist.

Anyway, back to the code. On line 2, we define a variable uppercount as (dec (count numlist)). ‘count’ counts the number of elements in a list, and ‘dec’ decrements its argument by 1, so this statement assigns (size of list – 1) to the variable uppercount.

On line 3, we begin a loop. We discussed loops in an earlier post. Here we initialize lower and upper as instructed by the algorithm. You might wonder, by the way, why we used a separate ‘def’ statement to define uppercount and then use this variable to initialize upper. Why couldn’t we just initialize upper to (dec (count numlist)) directly in the loop’s parameter list? The answer seems to be that there is a bug in the Clojure compiler that complains about a mismatch in data types if you try to put a function call in a loop’s parameter list. At least I’m assuming it’s a bug – there doesn’t seem to be any reason why you shouldn’t be able to do this.

Line 5 implements step 2 in the algorithm, and terminates the function if target is not found. Line 6 opens a let statement, and calculates mid and midvalue. Note the use of the quot function, which calculates the integer quotient, discarding any remainder. Recall that variables defined within a let have a scope that is restricted to the let.

Line 7 uses the nth function to find element number mid in numlist. The ‘nth’ function takes two arguments: the first is a list and the second is an integer giving the index of the required element.

Line 8 starts a ‘cond’ statement, which is a bit like a ‘switch’ statement in Java. A ‘cond’ consists of a series of pairs. Within each pair, the first element must be a predicate (returning true or false), and the second element is code that is to be run if the first element is true. This ‘cond’ tests the 3 conditions in the algorithm above.

If midvalue > target, then we make a recursive call with upper replaced by mid – 1 (remember ‘dec’ from above). Recall that within a loop, the ‘recur’ causes a recursive call to the loop statement, not to the enclosing function, so the loop is re-entered on line 3, with lower unchanged and upper set to (dec mid).

Line 10 handles the case where midvalue < target in a similar way. Line 11 ends the recursion if target has been found, and returns mid as its location in the list.

The ‘cond’ function allows the use of an ‘:else’ clause which is called if all the earlier predicates return false. Thus we could replace (= midvalue target) mid on line 11 by :else mid.

Advertisements
Post a comment or leave a trackback: Trackback URL.

Comments

  • Colin Hastie  On November 27, 2014 at 2:45 PM

    Don’t use `def` for locals. Use `let` instead.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: