What is Binary Search?

Binary search is an efficient algorithm for finding an item in a sorted array. It's like looking up a word in a dictionary: you don't start at page 1. You open to the middle, see if your word comes before or after, then repeat with the correct half.

How It Works:

1. Start with the middle element
2. Compare with target
3. If equal, found it!
4. If target is smaller, search left half
5. If target is larger, search right half
6. Repeat until found or array exhausted

Why It's Fast:

• O(log n) time: Cuts search space in half each step
• Efficient: Much faster than linear search (O(n))
• Simple: Easy to understand and implement

Requirements:

• Sorted data: Array must be sorted first
• Random access: Need to jump to middle elements

Example:

Finding "mouse" in a sorted dictionary:

1. Open to middle → "lion"
2. "mouse" comes after → search right half
3. Open to middle of right half → "rabbit"
4. "mouse" comes before → search left of that
5. Found "mouse"!

FAQ

Why is binary search O(log n)?

Each step eliminates half the remaining elements. With n elements, you need at most log₂(n) steps to find or determine it's not there.

Can binary search work on unsorted data?

No! Binary search requires sorted data. If data isn't sorted, you need linear search or sort first.