How to Find Your Number in a Sorted List: Binary Search Explained

What is binary search?

Binary search is another fairly intuitive way of searching. It's a very efficient logarithmic algorithm, and it's intuitive if you imagine you were searching through an actual physical dictionary.

Binary search relies upon the list that you're searching to be sorted.

How binary search works

Real-life analogy: A dictionary

So imagine you had a dictionary in front of you and you wanted to search for the word "ostrich". You wouldn't start at page one of the dictionary and then go to page 2 and then page 3 and then page 4.

You'd open the book somewhere in the middle, and then you'd be able to discard all of the letters to the left all of the pages to the left as you turn to them to the middle. Then you'd be able to get another section somewhere halfway between the stack, you cut that in half, and you'd get that page.

You'd keep repeating that process until you found the word that you were looking for.

Binary search algorithm

A binary search does something very similar. It relies on having a sorted list. Let's say it's 1024 items long. And what you do with binary search is you go to the middle item of this sorted list, and if that's the item you're looking for then, that's it. The search is over.

If the item is not the item you're looking for but is higher than the item that you're looking for in value in numerical value or in the latter value, depending on what it is that you're searching for. Then you can say, well, the item that I'm looking for must be in the left part of the list because I know they're sorted.

So if I've landed on the midpoint of this list and the item is higher in value than the number I'm looking for - I can get rid of all of the items; it’s right because I know that they are also going to be high. And then I repeat that process.

How binary search is efficient? In the first step, you get rid of half of the items that you're searching through, so your list of 1024 items is now 512 items, and then you repeat that process, discarding half of the items in each iteration. That’s how binary search works!

Also published on https://blog.icodes.tech/posts/Python-Binary-search.html.