Welcome back to 'Unlocking Algorithms'! In this section, we dive into a fundamental and incredibly powerful technique: Binary Search. If you've ever looked up a word in a dictionary or a name in a phone book, you've intuitively used a form of binary search. It's a prime example of the 'divide and conquer' strategy, where we repeatedly break down a problem into smaller, more manageable subproblems until we reach a solution.
The core idea behind binary search is simple: it works on sorted data. Imagine you have a sorted list of numbers, and you're looking for a specific number. Instead of checking each number one by one from the beginning (which would be a linear search, taking potentially a very long time for large lists), binary search makes a much smarter choice. It starts by looking at the middle element of the list.
Here's how it plays out:
- Check the Middle: Compare your target number with the middle element of the sorted list.
- Found It? If the middle element is your target number, you've found it! We're done.
- Too High? If your target number is less than the middle element, you know your target can only be in the left half of the list. You can completely discard the right half.
- Too Low? If your target number is greater than the middle element, you know your target can only be in the right half of the list. You can completely discard the left half.
We then repeat this process on the remaining half of the list, effectively halving the search space with each comparison.
graph TD;
A[Start with a sorted list]
B{Is the list empty?}
C[Target not found]
D[Pick the middle element]
E{Is middle element the target?}
F[Target found!]
G{Is target less than middle?}
H[Search the left half]
I[Search the right half]
A --> B
B -- Yes --> C
B -- No --> D
D --> E
E -- Yes --> F
E -- No --> G
G -- Yes --> H
G -- No --> I
H --> B
I --> B
Let's illustrate with an example. Suppose we have the sorted list: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] and we are looking for the number 23.
First, we find the middle element. The list has 10 elements, so the middle index is (0 + 9) / 2 = 4.5, we'll take the floor which is index 4. The middle element is 16.
Is 23 equal to 16? No.
Is 23 less than 16? No.
So, 23 must be greater than 16. This means we can discard the left half of the list (elements 2, 5, 8, 12) and focus on the right half: [23, 38, 56, 72, 91].