Searching techniques

Learning outcomes

Select a search method from its preconditions, trace a binary search interval, and avoid boundary errors.

4.1 Linear search

Linear search inspects elements one at a time until it finds the key or reaches the end. It works whether or not the array is sorted. A useful interface returns a success flag and writes a valid index only on success; this avoids confusing “not found” with index zero.

for i = 0 through n − 1:
    if a[i] == key: return found at i
return not found

For {23, 12, 18, 7, 45} and key 7, the comparisons are 23, 12, 18 and 7. Four elements are inspected. If duplicates exist, this version finds the first occurrence. Best-case time is Θ(1), worst-case time Θ(n), and auxiliary space Θ(1).

4.2 Binary search

Binary search requires an array sorted according to the same ordering used by the search. Inspect the middle value. If the key is smaller, discard the right part; if larger, discard the left part. An arbitrary linked list does not offer the constant-time midpoint access assumed by the array version.

Use a half-open candidate interval [lo, hi): lo is included and hi is excluded. Initially lo = 0 and hi = n. The interval is empty when lo == hi.

lo = 0; hi = n
while lo < hi:
    mid = lo + (hi − lo) / 2
    if a[mid] == key: return found at mid
    if a[mid] < key: lo = mid + 1
    else: hi = mid
return not found

The invariant is: if the key exists and has not been returned, an occurrence remains in [lo, hi). Each unsuccessful step strictly shrinks that interval. Computing the midpoint as lo + (hi − lo)/2 avoids the possible overflow of lo + hi.

4.3 Worked trace

Search for 18 in {7, 12, 18, 23, 45, 60}.

For missing key 20, the same first two steps lead to index 2; 18 is too small, so lo becomes 3. Now lo equals hi and the search stops. No access at index 3 is required after the interval becomes empty.

Binary search takes O(log n) worst-case time and Θ(1) auxiliary space in its iterative form. This version may return any matching index when duplicates occur. Finding the first or last occurrence requires a modified boundary search. The laboratory uses such a lower-bound variant: it returns the first matching index, or n when absent. Its return convention differs from the success-flag interface described for linear search above.

4.4 Include preparation in the decision

For one lookup in an unsorted array, sorting first may cost more than linear search. For many searches on mostly unchanged data, an initial sort can be worthwhile. Binary search also does not make insertion into a sorted array logarithmic: finding the position is O(log n), but shifting values may still take Θ(n).

Practice

1. Trace binary search for 6 and 60 in the six-element array above.
2. What happens when n is zero in the half-open algorithm?
3. Give an example showing why binary search is invalid on unsorted input.
4. Modify the algorithm to return the first index whose value is not less than the key. State how you would then test whether the key exists.

/* C11. teaching example. Logical length is separate from capacity. */
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>

static bool insert(int a[], size_t *n, size_t cap, size_t pos, int value)
{
    if (*n > cap || *n == cap || pos > *n) return false;
    for (size_t i = *n; i > pos; --i) a[i] = a[i - 1];
    a[pos] = value;
    ++*n;
    return true;
}
static bool erase(int a[], size_t *n, size_t pos, int *removed)
{
    if (pos >= *n) return false;
    *removed = a[pos];
    for (size_t i = pos; i + 1 < *n; ++i) a[i] = a[i + 1];
    --*n;
    return true;
}
/* Return n if the value is absent. */
static size_t linear_search(const int a[], size_t n, int key)
{
    for (size_t i = 0; i < n; ++i) if (a[i] == key) return i;
    return n;
}
/* Precondition: a[0..n) is in nondecreasing order. Returns first match. */
static size_t binary_search(const int a[], size_t n, int key)
{
    size_t lo = 0, hi = n;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;
        if (a[mid] < key) lo = mid + 1;
        else hi = mid;
    }
    return lo < n && a[lo] == key ? lo : n;
}
int main(void)
{
    int a[5] = {10, 30, 40}, removed = 0;
    size_t n = 3;
    assert(insert(a, &n, 5, 1, 20));
    assert(insert(a, &n, 5, 4, 50));
    assert(!insert(a, &n, 5, 5, 60));
    assert(!insert(a, &n, 5, 6, 60));
    assert(binary_search(a, n, 30) == 2);
    assert(binary_search(a, n, 99) == n);
    assert(linear_search(a, n, 50) == 4);
    assert(erase(a, &n, 2, &removed) && removed == 30);
    assert(!erase(a, &n, 4, &removed));
    printf("After deletion:");
    for (size_t i = 0; i < n; ++i) printf(" %d", a[i]);
    putchar('\n');
    int duplicate[] = {1, 2, 2, 2, 3};
    assert(binary_search(duplicate, 5, 2) == 1);
    assert(binary_search(a, 0, 10) == 0);
    assert(linear_search(a, 0, 10) == 0);
    n = 0;
    assert(!erase(a, &n, 0, &removed));
    assert(insert(a, &n, 5, 0, -1) && a[0] == -1);
    puts("arrays/search tests passed");
    return 0;
}