Binary Search

What is Binary Search?

Binary search finds an answer by repeatedly removing half of the remaining possibilities. The data does not always need to be a literal array, but the decision must move in one predictable direction.

You need array indexes, integer division, and the meaning of sorted order. The short version is: check the middle, prove which half cannot contain the answer, and continue in the other half.

The Core Idea: Remove Half

In LC 704: Binary Search, the array is [1,3,5,7,9,11,13,15,17,19] and the target is 11. The middle value tells us whether 11 is to the left, at the middle, or to the right.

Why can we ignore an entire half? If the middle value is smaller than 11, every value to its left is also smaller. None of those values can be the target.

It is like finding a word in a paper dictionary. After opening near the middle, alphabetical order tells you which half to close permanently.

How the Search Space Shrinks

The Rule You Keep True

At the start of every loop, any possible answer must lie inside the current search interval. Every boundary update must keep that statement true while making the interval smaller.

The middle comparison changes by problem:

• Exact search compares array[mid] with a target.
• Insertion or boundary search asks whether mid belongs before or after the first valid position.
• Peak search compares array[mid] with array[mid + 1] and follows the rising side.
• Search on an answer runs a feasibility check such as whether Koko can finish at a chosen speed.

Find First and Last Position is the one that usually trips us up. Finding any copy is easy. Finding the boundary requires continuing after a match and preserving that match as the best answer so far.

Picking the Right Shape

From Rule to Code

1. Choose whether the search interval is inclusive or half-open and keep that choice consistent.
2. Calculate mid from the current boundaries.
3. Check the middle value or condition.
4. Return a match, or move one boundary past mid.
5. Return the saved boundary or not-found result when the interval is empty.

The interval becomes strictly smaller after every iteration, so the search finishes after O(log n) checks and uses O(1) extra space.