Searching an Array: Linear and Binary

Where you are: Week 0 review > Searching an array

Try This First

Your binary search returns -1 for a value you can see in the array. Name the most likely cause before reading on.

Before You Start

Check each box you can do from memory. A box you cannot check yet is not a problem; it points you to a quick refresher, not a grade.

• I can read the element at position i of an array xs using xs[i], counting from zero.
• I can write a counted for loop that visits every index of an array.
• I can describe what an accumulator variable does across a loop.

See Arrays and Accumulator Patterns if any box above felt shaky.

What You Need To Walk In With

Walk into the next class able to state these:

• A search returns the index of a match, or -1 when the value is absent. Because the answer is an index, a search uses a counted for, not a for-each.
• Linear search checks each element in order; it works on any array.
• Binary search requires a sorted array and halves the remaining range on each step, so it is much faster on large sorted data.

You should be able to: write indexOf for a linear search, and state the precondition for binary search.

How It Works

Linear search

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

It returns the index of the first match, or -1 if the loop finishes with no match. A for-each cannot do this: it exposes the value but not the index, and the index is the answer.

Binary search

Binary search works only on a sorted array. It tracks a range with low and high, checks the middle, and discards the half that cannot hold the target:

int low = 0, high = xs.length - 1;
while (low <= high) {
    int mid = (low + high) / 2;
    if (xs[mid] == target) { return mid; }
    else if (xs[mid] < target) { low = mid + 1; }
    else { high = mid - 1; }
}
return -1;

Each step halves the range, so binary search on a sorted array of a million elements needs about twenty checks, while linear search may need a million.

Worked Example: Predict, Then Check

int[] xs = {2, 4, 6, 8};   // sorted
// binary search for 6: low=0 high=3 mid=1 (xs[1]=4 < 6, low=2)
//                      low=2 high=3 mid=2 (xs[2]=6) -> found at index 2

Predict the returned index for target 6.

A Common Mistake

Running binary search on an unsorted array returns -1 even when the target is present, because the order-based decision to move low or high discards the wrong half. Binary search is not “just a faster search”; it has a precondition. Sort first, or use linear search on unsorted data. (Source: BJP (Reges and Stepp), Ch 13.)

Go Deeper (optional)

For the curious: halving the range each step is why binary search is described as logarithmic. The number of steps to narrow n elements to one is about the number of times you can halve n, which is the base-two logarithm of n. That is the same idea as asking how many digits a number needs, and it connects directly to what a logarithm measures.

Check Yourself

Close the notes and answer each one from memory, then reveal it. Pulling an idea back from memory is one of the strongest ways to make it stick.