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

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

tldt arrow
Read on Terminal Reader

Too Long; Didn't Read

Binary search is another fairly efficient way of searching for things. It's a logarithmic algorithm that relies on having a sorted list. 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. If not, you discard half of the items in the list (either from the left or right side depending on whether the current selection is lesser or greater than the search item). You again start in the middle of the new list and keep on repeating this process until you reach your desired search item.

Company Mentioned

Mention Thumbnail
featured image - How to Find Your Number in a Sorted List: Binary Search Explained
Icodes HackerNoon profile picture

@mohsiss

Icodes

A python programmer and founder of blog.icodes.tech programming blog ...

About @mohsiss
LEARN MORE ABOUT @MOHSISS'S EXPERTISE AND PLACE ON THE INTERNET.
react to story with heart

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.

image

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.

image

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.

RELATED STORIES

L O A D I N G
. . . comments & more!
Hackernoon hq - po box 2206, edwards, colorado 81632, usa