CLRS Algorithm a Day: Linear Search

A birthday, crunch time at work, Easter, experiments with MonoGame, and some other life things have gotten in the way of me continuing this series as frequently as I had planned, but never fear, back into the breach I go. Last time around, we started things off with Insertion Sort, which is the focus of Chapter 2.1 in my copy of the 3rd Edition. The natural next step to continue on to would be other sorting algorithms: selection sort, merge sort, quicksort, etc, etc. And we'll get there. But first I wanted to make a little diversion into one of the exercises for this chapter; writing a linear search.

I'm going to reproduce the problem definition from the exercise here, just to get us started:

Input: A sequence of n numbers such that A = {a₁, a₂, ..., a_n} and a value v.

Output: An index i such that v = A[ i ] or the special value NIL if v does not appear in A.

There's a bit more about writing loop invariants and proving that the algorithm is correct, if you were going to do this as a homework assignment. But that's incredibly dull, especially for something as self-evident as this. Let's get right to writing some code (github); this will be a short one.

Linear Search

There's not a whole lot to get fancy with with a linear search.

• We have the value we're searching for, and an array of values.
• We start at the beginning and compare the first item in the array with our search value, if it matches, we return that index.
• If not, we move on to the second item, and repeat
• If we get to the end and haven't found the value, then it isn't present, and we return our NIL sentinel value.

Since C# has 0-based arrays, and doesn't allow (yet) for any trickery like using negative indices to slice from the end, -1 is a reasonable sentinel value (and matches with the convention of the CLR Array.IndexOf function). So that leads pretty naturally to this, where we just use a for-loop:

public static int LinearSearch(this int[] a, int find) {
    for (var i = 0; i < a.Length; i++) {
        if (a[i] == find) {
            return i;
        }
    }
    return -1;
}

If we want to make it generic, that's also a cinch:

public static int LinearSearch<T>(this T[] a, T find) where T:IEquatable<T> {
    for (var i = 0; i < a.Length; i++) {
        if (a[i].Equals(find)) {
            return i;
        }
    }
    return -1;
}

Like last time, we can also make variants that don't require the data object type to implement IEquatable, like so:

public static int LinearSeach<T>(this T[] a, T find, IEqualityComparer<T> comparer) {
    for (int i = 0; i < a.Length; i++) {
        if (comparer.Equals(a[i], find)) {
            return i;
        }
    }
    return -1;
}

public static int LinearSearch<T>(this T[] a, T find, Func<T, T, bool> equals) {
    for (int i = 0; i < a.Length; i++) {
        if (equals(a[i], find)) {
            return i;
        }
    }
    return -1;
}

A recursive version is a little more fun, mostly because of how it inverts the control flow from the imperative version; we check our NIL-returning case first (Have we gone off the end of the array without finding the value?), then check if the current item is the value.

public static int LinearSearchRec<T>(this T[] a, T find, int i=0) where T : IEquatable<T> {
    if (i == a.Length) {
        return -1;
    }
    if (!a[i].Equals(find)) {
        return a.LinearSearchRec(find, i + 1);
    }

    return i;
}

Run-time Analysis: O(n)

We kind of gave it away in the title, but this is a linear-time algorithm, or O(n). Worst-case, we're searching for the item that is the last slot in the array, or we're searching for an item that isn't present, and we'll have to check every item in the array.

This is kind of a silly and trivial example to spend much time on, for it's own sake, but it isn't terrible for setting a baseline. There are a great many other searching problems that we'll encounter as we go through CLRS, and most of them much more sophisticated. We're starting at the start and going through, for pedagogical reasons...

Until next time, where we'll go back to sorting algorithms for a while. Hopefully without Harmonesque hiatuses in between....