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

Keep

Get amazing  articles about python programming

Read My Stories

Too Long; Didn't Read

Make resilience your competitive advantage

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

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps