What happens if I try to use binary search on an unsorted array?

The algorithm will fail unpredictably. It might accidentally find the number, or it might discard the half of the array that actually contains your target. Always sort the data first, or use a linear search.

What if there are duplicate numbers in the array?

Standard binary search will find *one* of the duplicates, but there is no guarantee which one (it might be the first, the last, or one in the middle). If you need to find the very first instance of a duplicate, you have to modify the algorithm to keep searching the lower half even after finding the target.

Is binary search always better than linear search?

Not always! If your list is very small (like 10 items), the overhead of setting up pointers and calculating the middle might actually be slightly slower than just scanning it. Also, if your data is unsorted, the time it takes to sort the array first $O(n \log n)$ is worse than just doing a single $O(n)$ linear search.

How does binary search work and why is it fast?

Binary search works by looking at the middle element of a sorted list and instantly discarding the half where your target cannot possibly live. By repeating this process, it zeroes in on the target in a fraction of the time it would take to check every item.

It is fast because it eliminates half of the remaining possibilities at every single step. Instead of counting one by one, the workload shrinks exponentially, allowing you to search massive datasets almost instantly.

What it is: The Dictionary Analogy

Imagine trying to find the word 'Tutor' in a physical dictionary. You wouldn't start at page one and read every single word. Instead, you'd open the book roughly in the middle. If you land on 'Monkey', you know 'Tutor' comes later in the alphabet, so you completely ignore the first half of the book.

Binary search does exactly this with computer data. It uses three markers: a 'start' pointer, an 'end' pointer, and a 'middle' pointer. It checks the middle value, compares it to the target, and then moves either the start or end pointer to narrow the search window by exactly half. This process repeats until the middle pointer lands on the exact target.

Why it works: The Power of Halving

The speed of binary search comes from its time complexity, which is $O(\log n)$ in Big O notation. This means the number of steps required grows logarithmically with the number of items.

If you have 100 items, checking them one by one (linear search) takes up to 100 steps. Binary search takes at most 7 steps. If you have 1,000,000 items, linear search takes a million steps, but binary search still only takes about 20 steps. Because it cuts the pile in half every time, the algorithm barely breaks a sweat even as the list gets enormously large.

How to recognize when to use it

The absolute golden rule of binary search is that the data must be sorted. If the dictionary is out of alphabetical order, opening it to the middle tells you absolutely nothing about where a word might be.

Whenever a problem tells you that an array or list is 'sorted', 'ordered', or 'monotonically increasing', an alarm bell should ring in your head. That is almost always a hint that you can optimize your solution by using binary search instead of checking every element.

Where students slip up

The most common mistake when writing a binary search is the infamous 'off-by-one' error. This usually happens when updating the pointers.

If your middle element is not the target, you must move your start pointer to $mid + 1$ or your end pointer to $mid - 1$ . If you just set the pointer to $mid$ , the algorithm might get stuck in an endless loop when the search window shrinks to just one or two elements. Always step completely over the middle element you just checked!

Worked through

Use binary search to find the index of the number 7 in the sorted array: $[1, 3, 5, 7, 9, 11]$ .

First, we set our pointers: $start = 0$ (value 1) and $end = 5$ (value 11).

Step 1: Calculate the middle index. $(0 + 5) / 2 = 2.5$ , which rounds down to index 2. The value at index 2 is 5. Since 5 is less than our target 7, we know 7 must be in the upper half. We update $start = mid + 1 = 3$ .

Step 2: Our new pointers are $start = 3$ and $end = 5$ . The new middle index is $(3 + 5) / 2 = 4$ . The value at index 4 is 9. Since 9 is greater than 7, the target must be in the lower half. We update $end = mid - 1 = 3$ .

Step 3: Our pointers are now $start = 3$ and $end = 3$ . The middle index is $(3 + 3) / 2 = 3$ . The value at index 3 is exactly 7. We found our target at index 3!

Questions students ask

Ask about this topic

Explain at

Where this comes from: Introduction to Algorithms by Thomas H. Cormen et al. · Khan Academy: Algorithms Unit · Grokking Algorithms by Aditya Bhargava