4.3.4.1–4.3.4.3 - Linear, binary and binary-tree search (C#)

Linear search

Linear search examines elements one at a time until the target is found or the collection ends. It works on unsorted data because it does not eliminate unseen elements using their values.

static int LinearSearch(int[] values, int target)
{
    for (int index = 0; index < values.Length; index++)
        if (values[index] == target) return index;
    return -1;
}

This method belongs in a class; it returns the first matching zero-based index, or -1 for absence. Searching [14, 6, 19, 6] for 6 checks index 0 then index 1 and returns 1. Searching for 8 checks all four elements then returns -1. An empty array executes no iteration and also returns -1.

With n elements, the best case finds the first element in constant time, $O(1)$. The worst case inspects n elements, so time is $O(n)$; average successful time is also linear under ordinary equally likely-position assumptions. Doubling n approximately doubles this worst-case work. An early return helps some inputs but does not change the worst-case order.

Binary search on ordered data

Binary search compares the target with a middle element and discards the half that cannot contain it. The array must be sorted in the same order used by the comparisons; otherwise the discarded half might contain the target.

Maintain inclusive bounds low and high. While low <= high, calculate a middle index. Equality ends the search. If the target is greater, set low = mid + 1; otherwise set high = mid - 1. Removing the middle item from the remaining interval is essential for progress.

static int BinarySearch(int[] values, int target)
{
    int low = 0, high = values.Length - 1;
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        if (values[mid] == target) return mid;
        if (values[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

Integer division rounds down here because the interval length is non-negative. The chosen midpoint formula also avoids adding two large bounds. Trace [3, 8, 12, 17, 21, 29, 35] for 29:

For 20, inspect 17, then 29, then 21; the bounds become low=4, high=3, so return -1. Each unsuccessful comparison approximately halves the interval. The worst-case number of iterations is $\lfloor\log_2 n\rfloor + 1$ for n≥1, giving $O(\log n)$. An empty array starts with high=-1 and returns -1 without indexing it. With duplicate values, this version returns a matching index, not necessarily the first.