Discovering Binary Search: Find Things Faster in Sorted Lists!
Binary Search is a clever way to find things quickly in a sorted list. Imagine you have a book with numbered pages and I tell you to find page 463. Instead of starting from page one and flipping through each page until you find it, Binary Search helps you find the page much faster.
Here’s how it works: You open the book somewhere in the middle, let’s say page 300. If the page number you’re looking for is smaller than 300, you know it must be in the first half of the book. So, you go to the middle of that first half, let’s say page 150, and check again. If the number you’re looking for is bigger than 150, you know it must be in the second half of the book. You keep dividing the remaining pages in half and checking until you find the page you’re looking for or realize it’s not in the book.
By doing this, you can quickly eliminate a large number of pages with just a few checks. In fact, in three operations, you can eliminate over 600 possible positions! Compare that to the slower way of checking one page at a time, which would take seven operations to eliminate only seven positions.
Binary Search is so powerful because it works in what we call Logarithmic time. This means the number of operations needed to find something grows very slowly as the number of positions increases. In fact, the worst-case scenario is that it would take log2(n) operations, where ’n’ is the number of positions in the sorted list. Logarithms are like the opposite of exponents, and they make Binary Search really efficient. For example, if you had to search through 480,000 positions, it would take around 18 operations to find what you’re looking for.
So when should you use Binary Search? It’s best to use it when you have a sorted list or array and you want to find something quickly. It’s much faster than the slower method of searching one by one. There are different ways to implement Binary Search and even other advanced techniques like Hash Tables that can make it even faster.
I hope this simple explanation of Binary Search has sparked your interest in algorithms. I plan to write more short articles like this, so make sure to follow and stay tuned for more.
