4.14 Searching Algorithms

What you need to know

• Linear (sequential) search: check each element from the start until found or the end is reached. Returns the index or −1. Works on any array or ArrayList.
• Linear search worst case: n comparisons (element absent or last).
• Binary search: requires a sorted array. Compare the target to the middle; if equal, done; if smaller, search the left half; if larger, the right half. Repeat until found or the range is empty.
• Binary search implementation uses low, high, and mid = (low + high) / 2; adjust high = mid - 1 or low = mid + 1; loop while low <= high.
• Binary search worst case: about log₂ n comparisons — for 1,000 elements, about 10. The exam asks "how many elements are examined" for a given target: trace the mid values.
• Binary search on an unsorted array gives wrong answers, not an error.
• Both searches can be written for ArrayLists using get and size.

Worked example

public static int binarySearch(int[] a, int target)
{
    int low = 0;
    int high = a.length - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (a[mid] == target) return mid;
        else if (a[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}
// a = {2, 5, 8, 12, 16, 23, 38}, target 23
// mid=3 (12) < 23 → low=4; mid=5 (23) → found. 2 comparisons.

Trace it yourself

Step through with the buttons, or use the ← → keys. Changed variables are highlighted.

Going deeper

The nuance, edge cases, and connections that turn a 3 into a 5.

• Linear search works on anything, needs no preparation, returns the index of the first match or −1 (or a boolean). Worst case n comparisons. It's the right choice for one-off searches on unsorted data.
• Binary search needs sorted data. low/high bracket the remaining range; mid = (low + high) / 2; compare, then discard half by moving low or high past mid. Loop while low <= high. If they cross, not found.
• Trace protocol: a table with columns low, high, mid, a[mid], action. One row per comparison. "How many elements are examined" = number of rows.
• mid uses integer division, so for an even-size range it picks the lower middle. With low = 0, high = 7, mid = 3, not 3.5 or 4.
• Adjust past mid: low = mid + 1 or high = mid - 1. Setting low = mid can loop forever when low and high differ by 1.
• Comparisons: up to ⌊log₂ n⌋ + 1. For n = 1000, 10. For a million, 20. Linear would be up to n.
• On an unsorted array, binary search doesn't throw — it just returns wrong answers (may miss a present element). The exam asks "why did this return −1 even though the element is there" → not sorted.
• On ArrayLists: same algorithm with get(mid) and size().

Mistakes that cost points

• Setting low = mid or high = mid. Off by one; possible infinite loop.
• Rounding mid up. Integer division rounds down.
• Miscounting comparisons. One per loop iteration. The found step counts.
• Using binary search on unsorted data. Wrong answers, not errors.

Practice questions

Written in the style of the real exam. Try each one before revealing the answer.