Faster Searching with Binary Search

Before we learn the shortcut, we need to understand the long way. Linear Search is when you check every item in a list, one by one, starting from the beginning. If you are looking for a specific card in a shuffled deck of $n$ cards, you might have to look at all $n$ cards before you find it. In Computer Science, we say this takes 'linear time' because the more items you have, the longer it takes in a straight line. While this works for small lists, it is incredibly slow for big data like Google searches or Instagram followers.

Binary search has one strict rule: the list MUST be sorted. This means numbers must go from smallest to largest ($1, 2, 3...$) or words must be in alphabetical order ($A, B, C...$). If the list is messy, the algorithm gets lost. Think of a phone book; because the names are sorted, you don't have to look at every page. You can jump around because you know exactly which direction the 'S' names are compared to the 'M' names. This 'direction' is what makes binary search so powerful.

The strategy of binary search is called Divide and Conquer. Instead of checking one by one, you jump to the exact middle of the list. You ask: 'Is my target higher or lower than this middle item?' If your target is higher, you instantly 'throw away' the entire bottom half of the list. You then repeat this with the remaining half. Every single step you take cuts the number of items you have to search in half! Mathematically, if you have $n$ items, you only need about $\log_{2}(n)$ steps to find your target.

The difference in speed is mind-blowing. For a list of $1,000$ items, Linear Search might take $1,000$ steps. Binary Search takes only $10$ steps. If you had $1,000,000$ items (one million), Linear Search could take a million steps, but Binary Search would finish in just $20$ steps! This is because $2^{20}$ is over a million. This efficiency allows computers to search through billions of records in the blink of an eye.