4.14 Searching Algorithms

4.14 Searching Algorithms

A searching algorithm examines a collection of values to determine whether a target exists and, often, where it occurs. The simplest question is deceptively powerful: how much of the collection must the program inspect before it can safely answer?

Linear search: check each element in order

A linear search—also called a sequential search—starts at the first element and examines values one at a time until it finds the target or reaches the end. It works on both sorted and unsorted data because it makes no assumption about how the elements are arranged.

For an array containing $n$ elements, a linear search may inspect only one element if the target is first, but it may inspect all $n$ elements if the target is last or absent. Its informal worst-case run time is therefore proportional to $n$, written as $O(n)$.

Worked example: finding a temperature

Suppose a weather station stores daily high temperatures:

$$ [72,\ 68,\ 75,\ 81,\ 69] $$

To search for $81$, the algorithm compares:

1. $72$ with $81$ — not equal
2. $68$ with $81$ — not equal
3. $75$ with $81$ — not equal
4. $81$ with $81$ — found at index $3$

A Java method can return the index where the target appears and return $-1$ when no match exists:

public static int linearSearch(int[] values, int target) {
    for (int i = 0; i < values.length; i++) {
        if (values[i] == target) {
            return i;
        }
    }
    return -1;
}

The return statement immediately ends the method when a match is found. If the loop finishes without returning, every element has been checked, so $-1$ communicates “not found.” If duplicate values occur, this implementation returns the index of the first occurrence encountered from left to right.

Key insight: Linear search needs no ordering, but it pays for that flexibility by potentially checking every element.

Binary search: eliminate half the possibilities

A binary search is faster, but it requires the data to be sorted. Instead of checking every element, it examines the middle value and discards the half that cannot contain the target.

For a sorted array, maintain two boundaries:

• low: the first index still under consideration
• high: the last index still under consideration

Calculate the middle index:

$$ \text{mid} = \frac{\text{low}+\text{high}}{2} $$

Java integer division discards any fractional part. If the middle value is less than the target, move low to mid + 1. If it is greater, move high to mid - 1.

Worked example: searching an ordered inventory

Consider the sorted array:

$$ [12,\ 19,\ 27,\ 34,\ 46,\ 53,\ 61,\ 78] $$

Search for $53$:

Step	low	high	mid	Middle value	Decision
1	$0$	$7$	$3$	$34$	Target is larger; discard indices $0$–$3$
2	$4$	$7$	$5$	$53$	Found at index $5$

The search examined only two values rather than scanning all eight. A binary search repeatedly halves the remaining search space, giving an informal run time of $O(\log n)$.

public static int binarySearch(int[] values, int target) {
    int low = 0;
    int high = values.length - 1;

    while (low <= high) {
        int mid = (low + high) / 2;

        if (values[mid] == target) {
            return mid;
        } else if (values[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1;
}

Comparing the algorithms

The choice depends on both the data and the operation being performed:

Feature	Linear search	Binary search
Requires sorted data?	No	Yes
Basic strategy	Check from beginning to end	Repeatedly inspect the middle
Worst-case run time	$O(n)$	$O(\log n)$
Handles an unsorted collection?	Yes	No
Common risk	Forgetting the final unsuccessful case	Incorrect boundary updates

Binary search is not “automatically better.” Sorting the data first has its own cost, and binary search is invalid if the order is not maintained. For a small or unsorted collection, linear search may be the clearer and more appropriate choice.

AP skill focus and misconception check

This topic develops Skill 2 — Develop Code when implementing search methods, Skill 3 — Analyze Code when tracing comparisons and boundary changes, and Skill 4 — Document Code and Computing Systems when explaining assumptions such as sorted input, return values, and run-time behavior.

Misconception check: “Binary search can search any array faster than linear search.”
Correction: Binary search depends on sorted data. On an unsorted array, discarding half the elements could discard the target, so the algorithm’s conclusion would be unreliable.

Retrieval check

An array contains $16$ sorted elements. A binary search looks at the middle element, finds that the target is larger, and continues. Which indices can still contain the target if the original indices are $0$ through $15$? Answer: indices $8$ through $15$, assuming the middle index was $7$. The lower half has been eliminated because every value there is too small.