Binary Search in Common-lisp: Complete Solution & Deep Dive Guide

scrabble tiles spelling the word library on a wooden table

Mastering Binary Search in Common Lisp: A Complete Guide from Zero to Hero

Binary Search is a cornerstone algorithm for any developer, offering a blazingly fast method to find elements in a sorted collection. This comprehensive guide breaks down its theory, implementation in Common Lisp, performance characteristics, and real-world applications, transforming you from a novice to an expert.

The Symphony of Numbers: Why Searching Matters

Imagine you've discovered a hidden library curated by a peculiar group of mathematician-singer-songwriters. They've composed a unique song for each of their favorite numbers, from the elegant 0 to the mysterious Kaprekar's constant, 6174. Their collection is vast, containing thousands of musical pieces.

You're eager to hear the song for your favorite number, say, 73. But the collection is enormous. You could start from the first song and listen to each one sequentially until you find it. This is a linear search. If you're unlucky and your number is near the end, this could take hours, testing your patience and dampening your curiosity.

This is a pain point every programmer faces: sifting through massive amounts of data to find a single piece of information. Fortunately, the mathematicians have a system. Their songs are meticulously organized and sorted numerically. This single property—being sorted—unlocks a superpower. Instead of a tedious linear scan, you can use a far more intelligent approach: Binary Search. This guide will teach you how to wield this power in Common Lisp.

What Exactly is Binary Search?

Binary search is a highly efficient searching algorithm that operates on the principle of "divide and conquer." Its fundamental requirement, and its greatest strength, is that the collection of data it searches through must be sorted. Think of it as the way you'd look up a word in a physical dictionary.

You don't start at the first page ("A") and flip through every single page until you find your word. Instead, you open the dictionary roughly to the middle. If your word comes alphabetically after the words on that page, you know your word must be in the second half of the book. You discard the entire first half and repeat the process on the remaining section. You keep halving the search space until you pinpoint the exact page.

This process of repeatedly dividing the search interval in half is what gives binary search its logarithmic time complexity, making it incredibly fast for large datasets. It systematically eliminates half of the remaining possibilities with each comparison, rapidly zeroing in on the target.

    ● Start with a sorted array [1..1,000,000]
    │
    ▼
  ┌───────────────────────────────┐
  │ Search Space: 1,000,000 items │
  └───────────────┬───────────────┘
                  │ Step 1: Compare with middle
                  ▼
  ┌───────────────────────────────┐
  │ Search Space: 500,000 items   │
  └───────────────┬───────────────┘
                  │ Step 2: Compare with new middle
                  ▼
  ┌───────────────────────────────┐
  │ Search Space: 250,000 items   │
  └───────────────┬───────────────┘
                  │ ... (approx. 20 steps total)
                  ▼
              ● Found!

Why is Binary Search a Foundational Algorithm?

The "why" behind learning binary search comes down to one critical concept in computer science: efficiency. As datasets grow from hundreds to millions or even billions of items, the difference between an efficient and an inefficient algorithm becomes the difference between an application that runs instantly and one that hangs for minutes or hours.

The Power of O(log n) Time Complexity

To appreciate binary search, we must compare it to its simpler cousin, linear search. In a linear search, you check every single element one by one. In the worst-case scenario, you have to check all n elements. This gives it a time complexity of O(n), meaning the time it takes grows linearly with the size of the input.

Binary search, however, has a time complexity of O(log n). The logarithm is the inverse of exponentiation. In simple terms, if you have a dataset of size n, log n represents the number of times you have to divide n by 2 to get down to 1. This number grows incredibly slowly.

Let's see the difference in practice:

For 1,024 elements: A linear search might take up to 1,024 comparisons. A binary search will take at most 10 (since 2¹⁰ = 1024).
For 1,048,576 elements: A linear search might take over a million comparisons. A binary search will take at most 20 (since 2²⁰ = 1,048,576).

This logarithmic scaling means that even for astronomically large datasets, binary search remains astonishingly fast. It is the go-to algorithm for searching in large, sorted arrays or data structures that mimic them.

How Does the Binary Search Algorithm Work?

The logic of binary search is elegant and methodical. It maintains a continuous sub-array (or "search space") of the original array where the target element might be located. Initially, this search space is the entire array. The algorithm is implemented using three pointers or indices: low, high, and mid.

Here is the step-by-step process:

Initialization:
- Set a `low` pointer to the first index of the array (0).
- Set a `high` pointer to the last index of the array (length - 1).
Iteration:
- Start a loop that continues as long as `low` is less than or equal to `high`. If `low` ever becomes greater than `high`, it means the search space has been exhausted and the element is not in the array.
Find the Middle:
- Inside the loop, calculate the middle index: `mid = floor((low + high) / 2)`. Using the floor ensures we always get a valid integer index.
Compare:
- Compare the element at the `mid` index with the target value.
- Case 1: Match Found. If `array[mid]` is equal to the target, the search is successful. Return the index `mid`.
- Case 2: Target is Smaller. If the target value is less than `array[mid]`, it means the target, if it exists, must be in the left half of the current search space. We can discard the right half by updating the `high` pointer: `high = mid - 1`.
- Case 3: Target is Larger. If the target value is greater than `array[mid]`, it must be in the right half. We discard the left half by updating the `low` pointer: `low = mid + 1`.
Termination:
- The loop continues, shrinking the search space with each iteration. If the loop finishes (because `low > high`), it means the element was not found. In this case, it's conventional to return a special value like `nil` or `-1` to indicate failure.

Visualizing the Pointer Logic

This ASCII diagram illustrates the decision-making process inside the loop, showing how the `low` and `high` pointers converge.

    ● Start (low=0, high=n-1)
    │
    ▼
    ┌────────────────────────┐
    │ Loop while low <= high │
    └───────────┬────────────┘
                │
                ▼
       Calculate mid = truncate((low + high) / 2)
                │
                ▼
    ◆ arr[mid] == target? ───── Yes ⟶ ● Return mid (Found)
    │
    No
    │
    ▼
    ◆ arr[mid] > target?
   ╱                    ╲
  Yes                    No
  │                      │
  ▼                      ▼
┌──────────────────┐   ┌──────────────────┐
│ high = mid - 1   │   │ low = mid + 1    │
└──────────────────┘   └──────────────────┘
  │                      │
  └─────────┬────────────┘
            │
            ▼ (loop back to top)

Common Lisp Implementation: A Deep Dive

Now, let's translate this logic into idiomatic Common Lisp. The solution provided in the kodikra.com learning module is a clean, iterative implementation using Lisp's powerful loop macro. We will analyze it piece by piece.

The Complete Code

This code is designed to be part of a larger system, defined within its own package for modularity.


(in-package :cl-user)
(defpackage :binary-search
  (:use :common-lisp)
  (:export :binary-find :value-error))

(in-package :binary-search)

(defun binary-find (arr el)
  "Finds the index of element 'el' in a sorted vector 'arr' using binary search.
   Returns the index if found, otherwise NIL."
  (loop
    with low = 0
    with high = (1- (length arr))
    for mid = (truncate (+ low high) 2)
    while (<= low high)
    do (cond
         ((> (aref arr mid) el)
          (setf high (1- mid)))
         ((< (aref arr mid) el)
          (setf low (1+ mid)))
         (t (return mid)))
    finally (return nil)))

Line-by-Line Code Walkthrough

Let's dissect this function to understand every component.

Package Definitions


(in-package :cl-user)
(defpackage :binary-search
  (:use :common-lisp)
  (:export :binary-find :value-error))
(in-package :binary-search)

(in-package :cl-user): This ensures we start in a clean, standard package before defining our own.
(defpackage :binary-search ...): This creates a new package named binary-search. Packages in Lisp are namespaces that prevent naming conflicts.
(:use :common-lisp): Our package will inherit all the standard symbols from the common-lisp package (like defun, loop, etc.).
(:export :binary-find :value-error): This makes the function binary-find and a potential condition value-error public, so they can be accessed from other packages.
(in-package :binary-search): This switches the current working package to our newly defined one. All subsequent definitions will belong to binary-search.

Function Definition


(defun binary-find (arr el)
  ...)

defun is the macro for defining a function.
binary-find is the function name.
arr and el are the parameters: arr is the sorted array (specifically, a vector in Lisp) and el is the element we are searching for.

The `loop` Macro

The core of the logic resides in the loop macro, which is one of Lisp's most flexible and powerful constructs for iteration.


  (loop
    with low = 0
    with high = (1- (length arr))
    ...

with low = 0: This is a loop clause that initializes a local variable low to 0 once at the beginning of the loop. This is our left pointer.
with high = (1- (length arr)): This initializes high to the last valid index of the array. 1- is a function that subtracts one from its argument. This is our right pointer.


    for mid = (truncate (+ low high) 2)

for mid = ...: This clause declares a variable mid that is re-calculated at the beginning of every iteration.
(truncate (+ low high) 2): This calculates the midpoint. truncate is used to handle the case where low + high is odd, effectively performing an integer division that rounds down (floor).


    while (<= low high)

while (<= low high): This is the loop's termination condition. The loop will continue as long as the search space is valid (i.e., the left pointer has not crossed the right pointer).


    do (cond
         ((> (aref arr mid) el)
          (setf high (1- mid)))
         ((< (aref arr mid) el)
          (setf low (1+ mid)))
         (t (return mid)))

do: This clause specifies the main action to perform in each iteration.
(cond ...): This is Lisp's multi-branch conditional, similar to a series of `if-else if-else` statements.
((> (aref arr mid) el) (setf high (1- mid))): The first condition. If the element at the middle index (accessed with aref) is greater than our target el, we know the target must be in the left half. We update high to shrink the search space.
((< (aref arr mid) el) (setf low (1+ mid))): The second condition. If the middle element is less than our target, the target must be in the right half. We update low accordingly.
(t (return mid)): The t clause is the "else" case. If neither of the above is true, it means (aref arr mid) must be equal to el. We've found our element! return immediately exits the loop and makes the function return the value of mid.


    finally (return nil)))

finally: This clause specifies an action to be performed after the loop terminates normally (i.e., the while condition becomes false). It is not executed if the loop is exited early via a return.
(return nil): If the loop finishes without finding the element, this line is executed, returning nil (Lisp's representation of false/null) to signal that the search failed.

Alternative Implementation: The Recursive Approach

While the iterative approach using loop is highly efficient and idiomatic in Common Lisp, it's also valuable to understand the recursive implementation. Recursion can often lead to code that more closely mirrors the mathematical definition of an algorithm.

A recursive binary search function typically uses helper function that takes the `low` and `high` indices as arguments.


(defun binary-find-recursive (arr el)
  "A wrapper function for the recursive binary search implementation."
  (labels ((search-recursive (low high)
             (when (<= low high)
               (let ((mid (truncate (+ low high) 2)))
                 (cond
                   ((= (aref arr mid) el) mid) ; Base case: Found
                   ((> (aref arr mid) el)
                    (search-recursive low (1- mid))) ; Recurse on left half
                   (t
                    (search-recursive (1+ mid) high))))))) ; Recurse on right half
    (search-recursive 0 (1- (length arr)))))

Analysis of the Recursive Version

Structure: We use labels to define a local helper function search-recursive. This is a common Lisp pattern to create recursive helpers without polluting the global namespace. The main function binary-find-recursive simply kicks off the process by calling the helper with the initial bounds of the entire array.
Base Case: The recursion must have a base case to stop. There are two:
1. The element is found: ((= (aref arr mid) el) mid). The function returns the index.
2. The search space is empty: (when (<= low high) ...). If low becomes greater than high, the `when` condition is false, the block doesn't execute, and the function implicitly returns `nil`.
Recursive Step: If the element is not at `mid`, the function calls itself with updated `low` or `high` bounds, effectively performing the search on a smaller sub-array.

Iterative vs. Recursive: Which is Better?

For binary search, the iterative version is generally preferred in production code for a few reasons:

Performance: Iteration avoids the overhead of function calls, which can make it slightly faster.
Stack Depth: Each recursive call adds a frame to the call stack. For extremely large arrays, a recursive implementation could theoretically lead to a stack overflow error, though this is less of a concern in modern Lisp implementations with tail-call optimization (TCO). The provided recursive code is in a tail-call position, so a good compiler would optimize it into an iterative loop anyway.
Clarity: While recursion can be elegant, the `loop` macro in Common Lisp is often just as clear and more direct for this type of problem.

Understanding both approaches, however, makes you a more versatile programmer. You can explore both styles in the Common Lisp modules on kodikra.com.

Where and When to Use Binary Search

Binary search is not a universal solution. Its power is tied directly to its precondition. Knowing when to use it is as important as knowing how it works.

Ideal Use Cases

Large, Static, Sorted Datasets: This is the perfect scenario. Think of searching for a user ID in a database table indexed by that ID, or finding a specific commit in a Git history (`git bisect` is a form of binary search).
Implementing Higher-Level Data Structures: Binary search is the core search operation in binary search trees (BSTs) and other related structures.
Finding First/Last Occurrence: With slight modifications, binary search can efficiently find the first or last occurrence of a non-unique element in a sorted array.
Numerical Problems: It can be adapted to find the square root of a number or find the point where a monotonic function crosses a certain value.

When to Avoid Binary Search

The following table summarizes the key trade-offs to consider.

Pros / Strengths	Cons / Weaknesses
Extreme Efficiency: O(log n) time complexity is exceptionally fast for large datasets.	Requires Sorted Data: The single biggest limitation. If the data is not sorted, the algorithm will not work correctly.
Simple to Implement: The core logic is straightforward and requires only a few variables.	Sorting Overhead: If the data arrives unsorted, you must first pay the cost of sorting it (typically O(n log n)), which may negate the benefit of a fast search.
Low Memory Usage: The iterative version uses a constant amount of extra memory (O(1) space complexity).	Inefficient for Small Datasets: For very small arrays (e.g., < 20 elements), the overhead of the logic might make a simple linear search just as fast or faster.
Versatile: The core idea can be adapted to solve a wide range of problems beyond simple searching.	Poor for Dynamic Data: If elements are frequently inserted or deleted, maintaining a sorted array can be expensive (O(n) for each operation). Data structures like balanced binary search trees or hash tables are better suited for dynamic data.

Frequently Asked Questions (FAQ)

What is the time and space complexity of binary search?

The time complexity is O(log n) because the search space is halved in each step. The space complexity for the iterative version is O(1) as it only uses a few variables regardless of the array size. The recursive version has a space complexity of O(log n) due to the call stack depth.

Can binary search be used on an unsorted array?

Absolutely not. The algorithm's correctness depends entirely on the sorted property of the data. If the array is unsorted, the assumption that you can discard half the array after a comparison is false, and the algorithm will produce incorrect results or fail to find elements that are present.

Is binary search always better than linear search?

For large, sorted arrays, yes, by a massive margin. However, if the array is small, or if the data is unsorted and you only need to perform one search, the cost of sorting the array first (O(n log n)) would make a single linear search (O(n)) much faster.

What happens if the target element appears multiple times in the array?

The standard binary search algorithm is not guaranteed to find any specific instance of a repeated element. It will find one of the occurrences, but it might be the first, last, or one in the middle, depending on the data. Modified versions of binary search are required to reliably find the first (lower bound) or last (upper bound) occurrence.

Why calculate the middle as `(low + high) / 2`? Is there a risk?

In languages with fixed-size integers (like C++ or Java), `low + high` can cause an integer overflow if the array is very large. The safer way to write it in those languages is `low + (high - low) / 2`. In Common Lisp, integers have arbitrary precision, so overflow is not an issue. The direct formula is perfectly safe and clear.

How does binary search compare to a hash table lookup?

A hash table (or `hash-map` in Lisp) provides an average time complexity of O(1) for lookups, which is even faster than binary search's O(log n). However, hash tables have their own trade-offs: they require more memory (higher space complexity), do not keep elements in a sorted order, and are not suitable for "range" queries (e.g., finding all elements between X and Y).

Conclusion: The Art of Efficient Searching

Binary search is more than just a piece of code; it's a fundamental problem-solving paradigm. It teaches us the power of the "divide and conquer" strategy and the profound impact of algorithmic efficiency on application performance. By mastering its implementation in Common Lisp, you've added a critical tool to your software engineering toolkit.

You've seen how its logarithmic complexity allows it to handle massive datasets with ease, a feat that a simple linear search could never achieve. You've walked through both iterative and recursive implementations, understanding the trade-offs of each. Most importantly, you now know when to use this powerful algorithm and, just as crucially, when to choose a different tool for the job.

This knowledge is a key step in your developer journey. To continue building on this foundation, explore the next module in the kodikra.com Common Lisp learning path and deepen your understanding of data structures and algorithms.

Disclaimer: All code examples are written for modern Common Lisp implementations (like SBCL 2.4.x or later). The core logic is timeless, but specific library functions and performance characteristics may vary between implementations.

Published by Kodikra — Your trusted Common-lisp learning resource.

kodikra

Search this blog