Binary Search

Binary search is the first algorithm most people meet that feels like real computer science: it is clever, it is fast, and it is everywhere. Master it and you will find its pattern — 'halve the search space, decide which half to keep' — in databases, in debugging, in the way a large language model finds the most likely next word, and in the tools that let an AI system look up information from millions of documents. This concept sits at the very beginning of your Algorithms and Complexity path. Once you have it, the natural next steps are Loop Invariants (which will let you prove that your binary search is correct), Big-O Notation (which will let you say precisely how fast it is), and then Merge Sort and Quicksort — the sorting algorithms that produce the sorted lists binary search depends on. With those, you will be ready for Balanced Trees and B-Trees, which are how real databases keep their data organised. Binary search is the first rung on a very tall ladder, and every rung above it assumes you can stand firmly on this one.

Suppose you have a phone book (the paper kind) with 1000 pages, and you need to find the name 'Raman'. You could start on page 1 and flip forward one page at a time, checking every name. If you were unlucky, that would take 1000 flips. But nobody actually does that. You open the book roughly in the middle, see that 'M' is there, and you know immediately that 'Raman' (which starts with 'R') cannot be anywhere in the first half — 'R' comes after 'M' alphabetically, so the first half of the book is entirely 'A'-to-'M' names. You throw away that half without looking at a single page of it. Now your book is half the size. You open the middle of the remaining half, see 'S', and know that 'Raman' must be before 'S', so the second half of what remains is useless. Half again. Each time you look at exactly one page, and you eliminate half of every page you did not look at. After a handful of checks, you are down to one page, and there is the name. That is binary search: you are not searching faster — you are searching *less* by eliminating half the remaining search space with every single comparison. The word 'binary' just means 'two choices' — each step asks: is what I want in the left half or the right half? And then you move to that half and ask again. The key trick works only because the data has an order: alphabetical order in the phone book, or numeric order in a sorted list of numbers. If the pages were in random order, opening to the middle would tell you nothing about where 'Raman' is — you could not eliminate anything. Order is what makes halving possible. That is why binary search requires sorted input: the order is what tells you which half to discard. With a million entries, the difference is stark. Checking one by one could take a million steps. Binary search needs at most about twenty comparisons — because 2 raised to the 20th power is already over a million, so twenty halvings reduce any search space of that size to a single item. Twenty checks versus a million. That is the whole point of the algorithm.

Think of finding a word in a dictionary. You do not start at 'A' and read every entry. You open roughly halfway, see the word 'M'. Your word begins with 'P', so you know the first half of the dictionary — everything from 'A' through 'M' — is useless. You do not glance at it again. You now have a dictionary that is half the size. Open that in the middle, see 'R'. Your 'P' is before 'R', so the entire back half of what remains is thrown away. Now you are holding a dictionary a quarter of the original size. Open the middle again, see 'O'. 'P' is after 'O', so the front half of this quarter goes. Each glance at one page eliminates half of the remaining book. After a handful of glances, the book is reduced to a single page carrying your word. This analogy works beautifully because the mechanism is identical: each comparison halves the search space, and the order of the entries is what makes the halving valid. The analogy stops working in one particular way: the dictionary looks up words, which have a natural order (alphabetical), but binary search works on anything with a comparable order — numbers, timestamps, or even a list of names sorted by last name. Also, the dictionary is a physical object: you can flip to the middle of the remaining pages by feeling the thickness. In a computer, you do not feel thickness — you compute a middle index (the offset of the middle element) and then decide: the middle element is too big, so the answer must be in the lower half; or the middle element is too small, so the answer is in the upper half. The dictionary analogy also quietly assumes the word exists. If it does not, you will eventually get down to one page, search it thoroughly, and conclude 'not present'. Binary search handles that too: the process ends with an empty range, and you know the target is absent.

Binary search is the algorithm that locates a target value in a sorted sequence by repeatedly comparing the target to the middle element and eliminating the half that cannot contain it, until the target is found or the search range is empty.

This concept is your first real algorithm, and it builds on one thing you already know: how to compare two numbers (is this one less than, equal to, or greater than that one?). It is also your first encounter with a loop — a set of instructions that repeats — though we will write the loop by hand here, so you will learn what a loop is as we go. Its family tree in the Algorithms and Complexity world: it is the canonical example of 'divide and conquer' — a strategy where you solve a big problem by repeatedly splitting it into smaller, self-similar pieces. Merge Sort and Quicksort, neighbours in your library, use the same strategy. The efficiency of the approach is described by Big-O notation — a concept you have notes on, and which binary search is the perfect first example of: the number of steps grows not with the size of the list, but with the *logarithm* of its size. That word appears again in this page's mathematics section; by the end you will know exactly what it means. Correctly understanding why binary search never gets stuck requires the Loop Invariant — another nearby topic — but we will build up to that awareness here without formally naming it yet.