Searching

Overview

Searching means answering a simple question about a collection: is this value here, and if so, where? Almost every program asks this constantly. A contacts app finds a name, a game checks whether a key is held down, a database looks up a row by id, a compiler checks whether a word is a reserved keyword. The data lives in an array (which you met in the Arrays lesson), and searching is how you turn "I have a value" into "I have its position."

There are two foundational strategies, and the difference between them is one of the most important lessons in all of computing.

The first, linear search, is the obvious one: walk through the array from the start and compare each element to the value you want. It always works, on any array, in any order.

The second, binary search, is dramatically faster but comes with a strict precondition: the array must already be sorted. That is exactly why this lesson follows the Sorting overview lesson. Sorting is the price of admission for binary search. Once the data is in order, binary search can repeatedly cut the remaining range in half, the same way you find a word in a dictionary without reading every page.

Along the way you will meet big-O notation (O(n), O(log n)). Big-O is just a compact way to say "how does the amount of work grow as the data gets bigger?" It ignores constant factors and small details and focuses on the shape of the growth, because that shape is what decides whether your program stays fast when the input goes from a hundred items to a hundred million.

Why it matters

Search performance is rarely noticeable on tiny data and absolutely decisive on large data. Consider an array of one million sorted integers:

That gap is not a 10% improvement, it is the difference between an instant lookup and a program that stutters. Real systems lean on fast search everywhere: databases build indexes so lookups are logarithmic instead of linear; operating systems search sorted tables of processes and files; networking code searches routing tables; autocomplete searches dictionaries on every keystroke.

There is also a correctness angle. Binary search is famously easy to get almost right and subtly wrong. A binary search bug shipped in the Java standard library for nearly a decade because of an integer-overflow midpoint calculation. Learning to write it carefully, with the right interval convention, is a rite of passage that teaches you to reason precisely about loop boundaries, a skill that pays off across all of programming.

Core concepts

1. Linear search

Definition. Linear search (also called sequential search) examines elements one at a time, from the first to the last, returning the index of the first match or a "not found" marker if it reaches the end.

How it works. You keep an index i starting at 0. At each step you compare a[i] to the target. If they are equal, you are done. Otherwise you move to i + 1. The loop ends either at a match or when i reaches n.

target = 7
index:   0   1   2   3   4   5
array:  [3] [9] [1] [7] [4] [8]
         |   |   |   |
         3?  9?  1?  7?  -> match at index 3, return 3

Structure / cost. No precondition at all. Best case O(1) (match at the front), worst and average case O(n). It does the minimum number of comparisons that any algorithm could on unsorted data, because without order there is no way to rule out elements you have not looked at.

When to use it. The array is small, unsorted, or searched only a few times; or you need the first match by position; or the data changes constantly so keeping it sorted is not worth it.

When NOT to use it. Large data that is searched repeatedly. If you will do many lookups, sorting once and using binary search wins decisively.

Common pitfall. Forgetting that linear search returns the first match. If duplicates exist and you wanted the last one, linear search from the front gives the wrong answer.

Knowledge check (explain in your own words): Why does linear search work on an unsorted array while binary search does not?

2. Binary search

Definition. Binary search finds a target in a sorted array by repeatedly comparing the target to the middle element and discarding the half that cannot contain it.

How it works internally. You track a range of still-possible positions. Look at the middle element. If it equals the target, you are done. If the middle is less than the target, the target (if present) must be to the right, so discard the left half. If the middle is greater, discard the right half. Each step halves the range.

target = 13, sorted array
index:   0   1   2   3   4   5   6
array:  [1] [4] [6] [9] [13][20][31]

Step 1: lo=0 hi=7  mid=3  a[3]=9  < 13 -> go right, lo=4
Step 2: lo=4 hi=7  mid=5  a[5]=20 > 13 -> go left,  hi=5
Step 3: lo=4 hi=5  mid=4  a[4]=13 == 13 -> found at index 4

Structure / cost. Precondition: the array MUST be sorted in the order your comparisons assume (ascending here). Cost is O(log n) because the range halves each step: from n possibilities you reach 1 in about log2(n) steps.

The half-open interval [lo, hi). This lesson uses the convention that lo is included and hi is excluded. The range is empty exactly when lo == hi, which makes the loop condition cleanly while (lo < hi). When you go right you set lo = mid + 1 (mid is ruled out); when you go left you set hi = mid (mid is ruled out, and since hi is excluded you do not write mid - 1). Keeping one consistent convention is the single best defense against off-by-one bugs.

Meaning of [lo, hi):  candidates are indices lo, lo+1, ..., hi-1
Empty range:          lo == hi  -> stop, not found

When to use it. Sorted data searched many times, especially large data.

When NOT to use it. The data is unsorted (sort first or use linear search), tiny, or changes so often that maintaining sort order costs more than the searches save.

Common pitfall. Mixing interval conventions, e.g. using hi = n - 1 (an inclusive upper bound) but writing the loop as while (lo < hi). Inclusive bounds need while (lo <= hi) and hi = mid - 1. Pick one style and never mix.

Knowledge check (predict the output): With the array [2, 5, 8, 11] and the half-open algorithm above, how many comparisons of a[mid] happen when searching for 8? Trace lo, hi, and mid.

3. Big-O of searching

Definition. Big-O describes how an algorithm's work grows with input size n, ignoring constant factors.

Why O(log n) beats O(n) so much. Doubling the data adds one step to binary search but doubles the work of linear search. The table in "Why it matters" shows the practical effect: ~20 steps versus a million.

n          linear (worst)     binary (worst, ~log2 n)
10         10                 4
1,000      1,000              10
1,000,000  1,000,000          20

Pitfall. Big-O hides constants. For very small n, linear search can actually be faster because it has no setup and great cache behavior. Big-O tells you who wins as n grows, not who wins at n = 5.

Knowledge check (concept): If sorting an array costs O(n log n), is it worth sorting just to do one binary search instead of one linear search? When does sorting pay off?

Syntax notes

Binary search skeleton (half-open [lo, hi))

long binary_search(const int *a, size_t n, int target) {
    size_t lo = 0, hi = n;            // candidates are indices [lo, hi)
    while (lo < hi) {                 // stop when the range is empty
        size_t mid = lo + (hi - lo) / 2;  // overflow-safe midpoint
        if (a[mid] == target) {
            return (long)mid;         // found: return the index
        } else if (a[mid] < target) {
            lo = mid + 1;             // target is to the right; drop left half (incl. mid)
        } else {
            hi = mid;                 // target is to the left; drop right half (mid excluded by hi)
        }
    }
    return -1;                        // empty range: not present
}

Key syntax points:

• size_t is the correct unsigned type for array indices and sizes. Because it is unsigned, never write mid - 1 here (it could wrap around below 0); the half-open convention avoids needing it.
• The return type is long so a real index (0..n-1) is distinguishable from the -1 "not found" sentinel. Returning size_t would make -1 wrap to a huge value.
• const int *a signals the function does not modify the array.

Lesson

Two ways to search

Linear search checks every element, one by one. In the worst case it examines all n items, so its running time is O(n). The big-O notation here just describes how the work grows as the data gets larger.

Binary search is much faster, but it has one requirement: the data must already be sorted. Each step throws away half of the remaining elements, so the running time is O(log n). For a million items, that is about 20 steps instead of a million.

Writing it correctly

The C standard library provides bsearch in <stdlib.h>, which does the work for you.

If you write your own, use a half-open interval [lo, hi). This means lo is included but hi is not. Compute the midpoint as:

mid = lo + (hi - lo) / 2;

Writing it this way avoids two classic problems:

• Integer overflow — lo + hi can exceed the maximum value of the type on very large inputs. lo + (hi - lo) / 2 cannot.
• Off-by-one errors — the half-open interval keeps the loop boundaries consistent.

Code examples

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>

/* Linear search: works on any array, returns first matching index or -1. */
long linear_search(const int *a, size_t n, int target) {
    for (size_t i = 0; i < n; i++) {
        if (a[i] == target) {
            return (long)i;
        }
    }
    return -1;
}

/* Binary search on an ASCENDING-sorted array using the half-open range [lo, hi). */
long binary_search(const int *a, size_t n, int target) {
    size_t lo = 0, hi = n;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;   /* overflow-safe midpoint */
        if (a[mid] == target) {
            return (long)mid;
        } else if (a[mid] < target) {
            lo = mid + 1;                  /* search the right half */
        } else {
            hi = mid;                      /* search the left half */
        }
    }
    return -1;
}

/* Comparison function required by the standard library bsearch(). */
static int cmp_int(const void *pa, const void *pb) {
    int a = *(const int *)pa;
    int b = *(const int *)pb;
    return (a > b) - (a < b);   /* -1, 0, or +1 without risk of overflow */
}

int main(void) {
    int data[] = {1, 4, 6, 9, 13, 20, 31};   /* already sorted ascending */
    size_t n = sizeof data / sizeof data[0];

    int target = 13;

    long li = linear_search(data, n, target);
    long bi = binary_search(data, n, target);

    printf("linear_search(%d) -> %ld\n", target, li);
    printf("binary_search(%d) -> %ld\n", target, bi);

    /* Standard-library binary search; returns a pointer or NULL. */
    int *found = bsearch(&target, data, n, sizeof data[0], cmp_int);
    if (found != NULL) {
        printf("bsearch(%d) -> index %ld\n", target, (long)(found - data));
    } else {
        printf("bsearch(%d) -> not found\n", target);
    }

    int missing = 7;   /* not in the array */
    printf("binary_search(%d) -> %ld\n", missing, binary_search(data, n, missing));

    return 0;
}

What it does. It searches a 7-element sorted array for 13 three different ways (your linear search, your binary search, and the library bsearch), then confirms that a missing value 7 correctly returns -1. bsearch returns a pointer into the array, so we convert it to an index with pointer subtraction found - data.

Expected output:

linear_search(13) -> 4
binary_search(13) -> 4
bsearch(13) -> index 4
binary_search(7) -> -1

Edge cases worth noting. An empty array (n == 0): binary search's loop never runs and returns -1 immediately. Duplicates: this version returns some matching index, not necessarily the first. A target smaller than every element or larger than every element both correctly return -1.

Line by line

Walkthrough of binary_search(data, 7, 13) on {1, 4, 6, 9, 13, 20, 31}.

Line by line through the function body:

1. size_t lo = 0, hi = n; sets the candidate range to all of [0, 7).
2. while (lo < hi) checks the range is non-empty. 0 < 7 is true, so we enter.
3. mid = lo + (hi - lo) / 2 = 0 + 7/2 = 3. We examine a[3] = 9.
4. 9 == 13? No. 9 < 13? Yes, so the answer must be to the right; lo = 4. The range is now [4, 7).
5. Loop again: mid = 4 + (7-4)/2 = 4 + 1 = 5, a[5] = 20. 20 > 13, so the answer is to the left; hi = 5. Range [4, 5).
6. Loop again: mid = 4 + (5-4)/2 = 4, a[4] = 13. Equal, return 4.

Now trace the not found case, binary_search(data, 7, 7):

Notice the range shrinks to [3, 3), which is empty, so the loop exits and we return -1 without ever reading an out-of-range index.

Common mistakes

Mistake 1: Computing the midpoint as (lo + hi) / 2

size_t mid = (lo + hi) / 2;   // WRONG on very large arrays

Why it is wrong. If lo and hi are both close to the maximum representable value, lo + hi overflows before the division. With size_t (unsigned) it wraps to a small number, producing a wildly incorrect mid and likely an out-of-bounds access. This exact bug lived in the Java standard library for years.

size_t mid = lo + (hi - lo) / 2;   // CORRECT: (hi - lo) is small, no overflow

How to recognize it. It works fine in tests with small arrays and fails only on huge inputs, the worst kind of bug. Always use the subtraction form by habit.

Mistake 2: Running binary search on unsorted data

int data[] = {9, 1, 13, 4};        // NOT sorted
binary_search(data, 4, 13);        // result is meaningless

Why it is wrong. Binary search's entire logic depends on "everything left of mid is smaller, everything right is larger." If that is false, discarding a half can throw away the element you wanted. It may return -1 for a value that is actually present, or return the wrong index.

Fix. Sort first (qsort), or use linear_search if the data cannot be sorted.

How to prevent it. Treat "is this sorted?" as a precondition. In debug builds you can assert it.

Mistake 3: Mixing interval conventions

size_t lo = 0, hi = n - 1;          // inclusive upper bound...
while (lo < hi) {                   // ...but loop written for half-open!
    size_t mid = lo + (hi - lo) / 2;
    if (a[mid] < target) lo = mid + 1;
    else hi = mid;
}
// bug: misses the last element when target sits at index n-1

Why it is wrong. With an inclusive hi, the empty-range test must be lo > hi (so the loop is while (lo <= hi)) and the left step must be hi = mid - 1. Mixing the two styles silently skips elements.

Fix. Pick the half-open style of this lesson and stick to it everywhere: hi = n, while (lo < hi), hi = mid.

Mistake 4: Returning size_t so -1 is unusable

size_t binary_search(...) { ... return -1; }  // -1 wraps to SIZE_MAX!

Why it is wrong. size_t is unsigned, so the caller's if (result == -1) may not behave as expected and the "index" is enormous. Fix: return a signed type (long) for the index, or use an out-parameter plus a bool found return.

Debugging tips

Compiler warnings and errors

• comparison of integers of different signs or -Wsign-compare: usually from comparing a size_t (unsigned) with an int (signed). Keep indices size_t and return indices as long. Compile with -Wall -Wextra to surface these.
• Implicit declaration of bsearch/qsort: include <stdlib.h>.
• Wrong bsearch callback signature: the comparator must be int f(const void *, const void *). A mismatch triggers an incompatible-pointer warning.

Runtime errors

• Crash / AddressSanitizer: heap-buffer-overflow: you read a[mid] when the range was empty, or used the wrong loop condition. Build with -fsanitize=address and re-run; ASan points at the exact line.
• Infinite loop: typically lo = mid (instead of mid + 1) in the go-right branch. Because mid can equal lo, the range never shrinks. The fix is lo = mid + 1.

Logic errors

• Always returns -1 for present values: the array is not actually sorted, or it is sorted descending while your comparisons assume ascending.
• Returns the wrong duplicate: expected, this version returns any match. If you need the first match, search leftward after a hit or use a lower-bound variant.

Questions to ask when it does not work

1. Is the array genuinely sorted in the direction my comparisons assume? Print it.
2. Add a one-line trace inside the loop: printf("lo=%zu hi=%zu mid=%zu a[mid]=%d\n", lo, hi, mid, a[mid]); and watch the range shrink every iteration.
3. Does each branch strictly reduce the range (lo increases or hi decreases)? If not, that branch is the infinite-loop culprit.
4. Test the boundaries: empty array, single element, target at index 0, target at index n-1, target absent.

Memory safety

Memory safety and undefined behavior in search code

• Bounds. a[mid] is only safe when lo < hi and mid lies in [0, n). The half-open invariant lo <= mid < hi <= n guarantees this, which is the deep reason to keep the interval convention consistent. Break the invariant and you risk reading past the array, which is undefined behavior.
• Unsigned wraparound. size_t is unsigned: 0 - 1 is not -1, it is SIZE_MAX. Never write mid - 1 or hi - 1 without proving the value cannot be 0. The half-open form deliberately avoids subtracting 1 from an index.
• Overflow. lo + (hi - lo) / 2 cannot overflow for valid indices; (lo + hi) / 2 can. Prefer the safe form even when n is small, so the habit is automatic.
• Don't trust n. If a caller passes an n larger than the real array, every search can read out of bounds. The function cannot detect this; the caller must pass the true length, e.g. sizeof arr / sizeof arr[0] for a true array (not a pointer).
• No allocation needed. Both searches are O(1) extra space and free no memory, so there is nothing to leak here, but if you malloc the data you search, the owner of that buffer must still free it after the searches finish.
• const correctness. Declaring the parameter const int *a documents and enforces that searching does not mutate the data, preventing accidental writes.

Real-world uses

Where searching shows up

• Databases. A B-tree index is essentially generalized binary search on disk: each lookup touches O(log n) nodes instead of scanning the whole table. This is why a WHERE id = ? query on an indexed column is instant even on millions of rows.
• Standard libraries. C's bsearch, C++'s std::lower_bound, and Python's bisect are all binary search. They are the tested, overflow-safe versions you should reach for in real code.
• Operating systems & networking. Sorted symbol tables, page tables, and longest-prefix-match routing all rely on logarithmic search.
• Everyday features. Autocomplete, spell-check dictionaries, version-control "git bisect" (binary search over commits to find a bug), and game collision grids all use these ideas.

Professional best-practice habits

Beginner rules:

• Prefer the library (bsearch, qsort) over hand-rolled versions in production; only write your own to learn or when you need a custom variant.
• Always verify the sortedness precondition before binary searching; document it in a comment.
• Use clear names (lo, hi, mid, target) and one interval convention throughout the codebase.
• Compile with -Wall -Wextra -fsanitize=address,undefined while developing.

Advanced rules:

• Choose the algorithm from the access pattern: many searches over stable data → sort once + binary search; few searches or churning data → linear search.
• Mind cache behavior: for small n, linear search can beat binary search despite worse big-O.
• When you need the first or last of equal keys, use a lower-bound / upper-bound variant rather than plain binary search.
• Cover boundaries with unit tests: empty, single element, first, last, absent-below, absent-above, duplicates.

Practice tasks

Beginner

1. Linear search with count. Write long linear_search(const int *a, size_t n, int target) that returns the first index of target or -1. Then extend it to also print how many comparisons it made.

• Example: array {4, 8, 15, 16, 23, 42}, target 15 → returns 2, made 3 comparisons.
• Hint: a single for loop with a counter. Concepts: linear search, O(n).

2. Verify sortedness. Write int is_sorted_asc(const int *a, size_t n) returning 1 if the array is ascending (ties allowed) and 0 otherwise. Use it to guard a binary search call.

• Constraint: one pass, O(n), no extra array.
• Hint: compare each a[i] with a[i-1]. Concepts: precondition checking.

Intermediate

3. Half-open binary search from scratch. Implement long binary_search(const int *a, size_t n, int target) using [lo, hi) and lo + (hi - lo) / 2. Test it on an empty array, a single-element array, and a target at the very last index.

• Example: {2,5,8,11}, target 11 → 3; target 3 → -1.
• Hint: the loop is while (lo < hi); go-right is lo = mid + 1, go-left is hi = mid. Concepts: binary search, intervals, boundaries.

4. First occurrence (lower bound). Modify binary search to return the index of the first element equal to target when duplicates exist (or -1 if absent).

• Example: {1,2,2,2,5}, target 2 → 1 (not 2 or 3).
• Hint: on a match, do not return immediately; keep searching the left half (hi = mid) and remember the candidate. Concepts: lower-bound variant.

Challenge

5. Search a rotated sorted array. A sorted ascending array has been rotated at an unknown pivot, e.g. {6, 9, 12, 1, 3, 4}. Write long search_rotated(const int *a, size_t n, int target) that still runs in O(log n).

• Example: array above, target 3 → 4; target 7 → -1.
• Hint: at each step, one half is still sorted; decide which half is sorted by comparing a[lo] to a[mid], then check whether the target falls inside that sorted half. Concepts: binary search, invariants, careful case analysis.

Summary

Summary

• Two strategies. Linear search scans every element, works on any array, and is O(n). Binary search halves the range each step, is O(log n), but requires sorted data (the link back to the Sorting overview lesson).
• Big-O matters at scale. For a million items, binary search needs ~20 comparisons versus ~1,000,000 for linear. For tiny arrays the difference is negligible.
• Write binary search safely. Use the half-open interval [lo, hi): loop while (lo < hi), go right with lo = mid + 1, go left with hi = mid, and compute mid = lo + (hi - lo) / 2 to avoid integer overflow.
• Prefer the library. bsearch from <stdlib.h> (with a correct int cmp(const void*, const void*)) is the tested version for real code.
• Top mistakes to avoid. (lo + hi) / 2 overflow; binary searching unsorted data; mixing interval conventions; returning size_t so -1 wraps. Keep indices size_t, return the index as long, and always test the empty / single / first / last / absent boundaries.
• Remember: match the algorithm to your data. Sorted and searched often → binary search; small or unsorted or constantly changing → linear search.

Practice with these exercises

• Linear search
• Binary search