Linear and binary search

A question about a prefix

Searching asks whether a key occurs in a collection and, here, returns its first index. We connect bounded C arrays to the growth-analysis lesson: an algorithm's preconditions, result convention and counted operation must be stated before comparing costs. Prerequisites are array elements and valid indices, array parameters, loops, functions and algorithm-growth-and-asymptotic-bounds. This is an introductory search lesson, not complete algorithms coverage.

Our active data are a[0] through a[n-1], with 0 <= n <= CAP and CAP = 8. The caller supplies a live initialized int array containing at least CAP elements; n specifies how many are logically used. A zero in an unused slot is not searchable data. n = 0 is an empty prefix of that existing array, not a zero-length C array. No allocation or user input is needed.

Both functions return a SearchResult record. index is the smallest matching zero-based index on success, -1 for a valid search with no match, and -2 for a rejected pointer/length. comparisons counts only evaluated element-versus-key expressions: a[i] == key, a[mid] < key and the final a[lo] == key. Loop tests, index arithmetic, n checks and comparisons of indices are not counted. This is a defined cost model, not a timing measurement.

Linear search: inspect in order, whatever the value order

Linear search checks indices 0,1,... and returns at the first equality. It requires no sorted order. Before index i is tested, all indices smaller than i have been tested and contain no key. Thus returning i gives the first occurrence; exhausting the prefix proves absence. Incrementing i after failure makes progress; 0 <= i < n protects each read.

A row of unlabelled key boxes is a useful analogy: inspect boxes from the left, stopping at the first matching key. An empty row needs no inspection. This analogy does not imply that moving physical boxes or opening a box is part of our C cost model.

For n >= 1, a match first occurring at index p takes exactly p+1 equality comparisons. An absent key takes n. Best-case cost over all permitted arrays and keys is 1; worst-case is n. Hence these families have best Θ(1), worst Θ(n) element-key comparison cost. With n = 0 the count is 0. There is no single average-case formula without a probability model.

Binary search: use an ordering promise

Binary search here requires the active prefix to be sorted in ascending, nondecreasing order: a[i] <= a[i+1]. Duplicates are allowed. The function checks a non-NULL pointer and 0 <= n <= CAP; it does NOT scan to verify sorting. Sortedness is a caller precondition, as are valid storage and initialized values. Passing an unsorted prefix violates this contract and can produce an incorrect search result without producing the -2 error code. Linear search remains valid on that same unsorted prefix.

We find the lower bound: the first position whose value is at least key, or n if no such position exists. Keep the unresolved interval [lo,hi), including lo and excluding hi. Initially lo = 0, hi = n. While lo < hi, set mid = lo + (hi-lo)/2:

• If a[mid] < key, every position up to mid can be discarded because sortedness implies those values are also below key. Set lo = mid+1.
• Otherwise a[mid] >= key. It may be the first qualifying value, or an earlier one may qualify. Set hi = mid, retaining mid as a possible boundary even though it leaves the unresolved interval.

Do not return immediately on equality: that would find an arbitrary occurrence, not necessarily the first. Do not use hi = mid-1 with this half-open convention; that belongs to a different invariant.

On termination lo = hi is a boundary position, not automatically a match. First check lo < n; only then compare a[lo] == key. If lo == n, reading a[lo] would be outside the active prefix and may be outside the actual array when n == CAP. If lo < n but a[lo] is greater than key, the key is absent. Both absent cases return -1.

Complete bounded C11 program

#include <limits.h>
#include <stdio.h>

enum { CAP = 8 };
typedef struct {
    int index;       /* -2 invalid input; -1 absent; otherwise first index */
    int comparisons; /* only element-versus-key comparisons */
} SearchResult;

SearchResult linear_first(const int a[CAP], int n, int key) {
    SearchResult r = {-2, 0};
    if (a == NULL || n < 0 || n > CAP) {
        return r;
    }
    r.index = -1;
    for (int i = 0; i < n; ++i) {
        ++r.comparisons;
        if (a[i] == key) {
            r.index = i;
            return r;
        }
    }
    return r;
}

/* Caller promises a[0..n) is sorted in nondecreasing order. */
SearchResult binary_first(const int a[CAP], int n, int key) {
    SearchResult r = {-2, 0};
    if (a == NULL || n < 0 || n > CAP) {
        return r;
    }
    int lo = 0;
    int hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        ++r.comparisons;
        if (a[mid] < key) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    r.index = -1;
    if (lo < n) {
        ++r.comparisons;
        if (a[lo] == key) {
            r.index = lo;
        }
    }
    return r;
}

int main(void) {
    const int a[CAP] = {-4, 1, 1, 1, 7, 12, 0, 0};
    const int keys[3] = {1, 6, 20};
    for (int k = 0; k < 3; ++k) {
        SearchResult l = linear_first(a, 6, keys[k]);
        SearchResult b = binary_first(a, 6, keys[k]);
        printf("key=%d linear=(%d,%d) binary=(%d,%d)\n",
               keys[k], l.index, l.comparisons, b.index, b.comparisons);
    }
    return 0;
}

Exact output:

key=1 linear=(1,2) binary=(1,4)
key=6 linear=(-1,6) binary=(-1,4)
key=20 linear=(-1,6) binary=(-1,2)

Each printed pair is (index, comparisons). The six active values are [-4,1,1,1,7,12]; the last two allocated zero slots are inactive. INT_MIN and INT_MAX are also valid data/key values: the functions compare values directly rather than subtracting them. Subtracting extreme signed integers can overflow; comparison itself does not have that problem. limits.h supplies these constants for the accompanying author tests.

Read the C contract carefully

typedef struct names a record with two int fields. { -2, 0 } initializes them in declaration order. r.index selects a field. Returning the record copies its two values to the caller. const int a[CAP] in a function parameter is adjusted by C to a pointer to const int: the notation does NOT enforce an eight-element array or carry its capacity. The caller must actually meet the storage promise. The functions do not modify the array.

NULL is rejected even when n is zero, under this deliberately simple contract. The short-circuit || test rejects NULL or an invalid n before any array read. It cannot detect dangling pointers, undersized objects, uninitialized elements or concurrent changes. Every accepted non-NULL argument must be the address of the promised live initialized array; calls are sequential. The demonstration arrays are genuinely allocated with CAP elements.

++i adds one to i; == tests equality; < tests strict order; = assigns. The for loop in main chooses three keys; %d prints int fields and \n starts a new line. Bounds are tiny: lo, hi, mid and n remain between 0 and 8; counts are at most 8 for linear and 5 for binary. All shown index/count arithmetic fits int. The safe midpoint form avoids the general danger of computing lo+hi; it works because 0 <= lo <= hi <= n and hi-lo is representable.

Why binary search is correct and terminates

At the start of each loop iteration maintain:

1. 0 <= lo <= hi <= n.
2. Every active position strictly below lo has value < key.
3. Every active position at or above hi has value >= key.

The conditions outside the initial [0,n) interval are vacuous. When lo < hi, integer division gives lo <= mid < hi <= n, so the read a[mid] is valid. If a[mid] < key, sortedness proves condition 2 through mid and lo = mid+1 preserves all three conditions. Otherwise sortedness proves condition 3 from mid onward and hi = mid preserves them. Each update strictly decreases the nonnegative integer hi-lo; therefore the loop terminates.

At lo = hi, all earlier values are below key and all later active values are at least key. This establishes the lower-bound boundary. A guarded equality there establishes the first occurrence. A greater value or boundary n establishes absence. Empty n = 0 starts with lo = hi = 0, executes no loop, fails lo < n, and returns (-1,0) without accessing an element.

Worked trace 1: present key with duplicates

Use the program's active [-4,1,1,1,7,12], n = 6, key = 1. Linear checks index 0 (-4 == 1 is false) then index 1 (true): first index 1, two key comparisons.

The loop finishes at lo = hi = 1. Since 1 < 6, the final 1 == 1 succeeds. Binary uses three loop key comparisons plus one equality, total four. Returning at the first examined equality at index 3 would violate the required first-occurrence answer. This small input also shows that binary need not use fewer comparisons than linear on every query.

Worked trace 2: absent between stored values

Same array, key = 6. [0,6): mid 3, 1 < 6 true, so lo = 4. [4,6): mid 5, 12 < 6 false, so hi = 5. [4,5): mid 4, 7 < 6 false, so hi = 4. Termination gives boundary 4. The bounds test 4 < 6 permits reading 7; 7 == 6 is false. Result -1, three loop key comparisons plus one equality = four. Linear makes six failed equalities and returns -1. A lower-bound position is not proof of membership.

Worked trace 3: absent beyond the maximum

Same array, key = 20. [0,6): mid 3, 1 < 20 true, lo = 4. [4,6): mid 5, 12 < 20 true, lo = 6. The interval is now empty at [6,6). The test lo < n is false, so there is NO final element equality. Binary returns -1 after exactly two key comparisons; linear returns -1 after six. The two extra allocated zeros do not join the search.

Compare cost honestly

For the scalable version of this algorithm, an interval of length m > 0 shrinks to at most floor(m/2). For n >= 1, at most floor(log2 n)+1 loop iterations occur. The final membership test adds at most one element-key comparison, so an upper bound is floor(log2 n)+2. This is an upper bound, not a promise of equality for every query: the three traces use 4,4,2.

The lower-bound version deliberately continues narrowing even after encountering equality. Its best and worst comparison counts over inputs of length n >= 1 both grow as Θ(log(n+1)); for n >= 2 this can be written Θ(log n). It does NOT have the Θ(1) best case of a different binary-search algorithm that immediately returns an arbitrary matching midpoint. n = 0 has zero comparisons. No average-case claim is made. Both shown functions use Θ(1) auxiliary space in the scalable-array model; the caller's array storage is separate.

CAP = 8 makes this executable's allowed domain finite. Asymptotic statements concern a family of such algorithms with sufficiently large valid storage and representable indices, not unbounded inputs to this exact function. Fixed setup/checks are constant cost here.

If you add a full sortedness validation pass before each binary query, that pass checks n-1 adjacent pairs for n >= 1: Θ(n) work, making the combined worst-case per-query time Θ(n), not Θ(log n). Sorting an initially unordered array also has a separate cost and may change original indices. Do not hide either cost. For many searches on an unchanged already-sorted array, binary search can exploit the existing order; if you validate order once, account for that one-time work separately. This lesson does not implement a sorting or validation algorithm.

Key box

• Linear needs no value order; both functions return the first matching zero-based index.
• Binary requires an ascending, nondecreasing active prefix; pointer/length checks do not check that promise.
• Half-open [lo,hi) permits hi = n; midpoint is always below hi while the loop runs.
• Equality in the binary loop moves hi left; a guarded final equality confirms membership.
• Count the exact expressions in the given program, including the final equality only when it executes.
• Direct value comparisons support INT_MIN/INT_MAX without subtractive overflow.
• Lower-bound binary and early-return binary have different best-case behavior.

Two extra exercises

1. For the same six values and key = -5, trace both functions. Answer: linear makes six failed comparisons. Binary midpoints are 3,1,0; all three < -5 tests are false. Boundary 0 is valid but -4 == -5 is false, so binary returns (-1,4).
2. For a live int array with CAP slots whose active prefix is [2,2,2,2], find key 2. Answer: linear returns (0,1). Binary examines midpoints 2,1,0, moving hi each time, then checks a[0] == 2; it returns (0,4). Explain why an immediate return at midpoint 2 would break our contract.

Six original single-answer practice questions

Choose exactly one of four options. These are original practice questions.

1

For active [9,2,9,1] and key 9, what does linear_first return (index, comparisons)?

A. (0,1) B. (2,3) C. (-2,0) D. (0,4)

Answer: A

A is correct: index 0 equals 9, so the first comparison returns immediately.

B is incorrect: index 2 is a later occurrence; the function already returned at 0.

C is incorrect: linear search does not reject an unsorted prefix when pointer and length are valid.

D is incorrect: the early return prevents the remaining three comparisons.

2

For [-4,1,1,1,7,12], n=6 and key=1, what does the shown binary_first return?

A. (3,1) B. (1,3) C. (1,4) D. (-1,4)

Answer: C

A is incorrect: equality at midpoint 3 narrows hi rather than returning that duplicate.

B is incorrect: three loop comparisons omit the final membership equality.

C is correct: midpoints 3,1,0 lead to boundary 1; the final equality adds a fourth comparison.

D is incorrect: boundary 1 contains key 1, so membership succeeds.

3

When binary_first ends at lo=n for a valid call, what should happen next?

A. Read a[n] to confirm absence. B. Return -1 without evaluating an element equality. C. Return n as a matching index. D. Restart with hi=n-1.

Answer: B

A is incorrect: index n is outside the active prefix and can be outside storage at full capacity.

B is correct: lo<n is false; every active value is below key, so no match exists.

C is incorrect: valid matching indices are 0 through n-1; n is only a boundary.

D is incorrect: the invariant already proves absence, so restarting is unnecessary.

4

Which promise is required for binary_first but not linear_first?

A. Every value must be positive. B. All values must be distinct. C. The key must already occur. D. The active prefix must be nondecreasing.

Answer: D

A is incorrect: negative values and INT_MIN are allowed by both algorithms.

B is incorrect: duplicates are allowed; both return the first occurrence.

C is incorrect: both algorithms handle an absent key.

D is correct: only sorted order justifies discarding a whole side after the midpoint comparison.

5

For a live CAP-element array with n=0, what do both shown functions return?

A. (-1,0) B. (-2,0) C. (0,1) D. (-1,1)

Answer: A

A is correct: an empty valid prefix has no match and no element-key comparisons.

B is incorrect: zero length is valid with the promised live array; NULL would instead be rejected.

C is incorrect: an empty prefix has no valid element at index 0 to match.

D is incorrect: neither loop nor the guarded final equality reads an element.

6

In a scalable version, a full sortedness scan is performed before EACH binary query. What is the combined worst-case per-query time for n>=2?

A. Θ(1) B. Θ(log n) C. Θ(n) D. Θ(n²)

Answer: C

A is incorrect: the scan examines n-1 adjacent pairs and cannot be constant in growing n.

B is incorrect: this counts the binary phase but omits the full validation scan.

C is correct: Θ(n) validation plus O(log n) search is Θ(n) overall; these are sequential, not nested.

D is incorrect: adding linear and logarithmic phases does not create a quadratic nested scan.