Binary Search: Eliminate Half Each Time

Think it through · Start with a story

The cards are in order: 1, 3, 5, 7, 9. The girl wants to find 7. She looks at the middle card, 5. Why can she safely ignore the left half?

Break Down the Process

Follow the numbered steps, then explain them in your own words

The middle is 5Less than 7
Eliminate the left sideThose values are all at most 5
Keep the right side7, 9
Compare againFind 7

Binary search uses sorted order to narrow the range of candidates.

After comparing with the middle value, discard the side that cannot contain the target. Update the boundaries at each step so every position that could still match remains in the range.

Why Can You Eliminate Half Each Time?

Find 7 among cards sorted from smallest to largest. Gray cards have been ruled out.

Step 1 · Check the middle index, 2

13579

The middle value 5 is less than 7. It and the values to its left cannot be the target.

Step 2 · Keep the two values on the right

×××79

Using the middle index rounded down, compare the value at index 3: 7.

Step 3 · The target is found

×××7 ✓9

Return index 3, the fourth card. There is no need to check 9.

01Why Is Binary Search Fast?

If the data is already sorted from smallest to largest:

2  5  8  12  19  25  31  40

To find 25, you do not have to start at 2 and check every value. You can look at the middle first.

02How Can One Comparison Eliminate Half?

Check the middle value→Compare with target→Keep only the possible half

Because the array is sorted, if the target is greater than the middle value, all the smaller values to the left can be ruled out.

03How Do You Write Basic Code?

int left = 0;
int right = n - 1;

while (left <= right) {
    int mid = left + (right - left) / 2;

    if (a[mid] == target) {
        return mid;
    } else if (a[mid] < target) {
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}

return -1;

04Why Not Write mid as (left + right) / 2?

They look mathematically equivalent, but left + right may overflow before the division for some integer values.

left + (right - left) / 2

This is a common, safer way to calculate the middle.

05What Conditions Does Binary Search Require?

This form of binary search depends on the data being sorted.

06Which Match Does It Find When Values Repeat?

Ordinary binary search that returns as soon as it finds a match guarantees some matching position, but not necessarily the first or last one.

If a problem asks for “the first value ≥ x” or “the last value ≤ x,” design a boundary-focused binary search.

07Why Is Its Complexity O(log n)?

The remaining range is roughly halved each time:

1024→512→256→ ... →1

It takes only about 10 halvings to narrow a range of 1,024 elements down to one.

What You Have Learned

Binary search eliminates about half the candidates at each step.
Ordinary binary search on an array requires sorted data.
Update the range boundaries correctly, or the loop may never end.
With repeated values, ordinary binary search does not guarantee the first or last match.
Its time complexity is O(log n).

Next: Bubble Sort: Let the Bigger Values Float Up

Your Turn to Try

If the middle value is greater than the target, should you keep the larger values on the right?

Have you decided? Open to see the explanation

No. Keep the smaller values on the left. If the middle value is not the target, rule it out too, following the correct boundary rule.