Binary Search: The Divide and Conquer King

The Dictionary Trick

Imagine looking for the word "Python" in a physical dictionary. You don't start at 'A' and read every word — that would be Linear Search, checking every item one by one. Instead, you open the book to the middle.

• If you land on "M", you know "P" comes after "M" alphabetically, so you discard the entire left half of the book.
• You open the middle of the remaining right half. Maybe you land on "S". Now you discard the right half.
• You repeat this process, halving the search space each time, until you find "Python" or confirm it doesn't exist.

This is Binary Search: repeatedly cutting the problem in half.

The Requirements

Binary Search has two strict prerequisites that must both be satisfied:

1. Sorted Data: Binary Search only works if the array is already sorted. If the data is unsorted, you cannot make the "discard the left half" decision — you don't know which half contains your target.
2. Random Access: You need to jump to the middle index in constant time, O(1). Arrays support this. Linked Lists do not — to reach the middle of a Linked List, you must traverse from the beginning, which defeats the purpose.

The Power

Binary Search runs in O(log N) time. Logarithmic time is one of the most dramatic improvements in all of computer science:

Doubling the input size adds only one more step to Binary Search. This is why sorted indexes in databases can answer queries over billions of rows in milliseconds.