DEV Community

Cover image for Computer Science 4 Newbies - Understanding Binary Search
Igor Duca
Igor Duca

Posted on • Updated on

Computer Science 4 Newbies - Understanding Binary Search

As instructed by the first lesson of the book Understanding Algorithms, we must create a binary search that uses the "divide to conquer" method to find a number inside an array in the most performant way possible.

As instructed by the first lesson of the book Understanding Algorithms, we must create a binary search by explaining the context: what is a binary search?

There is a situation that can help you find it: suppose you have a book with 5,000 pages and you want to find a specific page in it. Let's imagine you're looking for page 487.ria that uses the "divide to conquer" method to find a number inside an array in the most performant way possible.

Image description

To find page 487 you can use some methods, one more efficient than the other:

Simple Search

The simple search method goes through the book page by page until you find page 487. taking into account that you take 1 second per page, it would take you 487 seconds to find the page.

Image description

Binary Search

The binary search method is a way to find the page in the most optimized way possible. with this method you would divide the book of 5000 pages in half, that is, you would open the book at page 2500 and ask yourself the following question: "the page I want is before or after the middle of the book?"

If your answer is "after", you will start searching for the specific page from page 2500 of the book,

If the answer is "before", you start searching for the specific page from 0 to 2499.

See in practice:

Image description

When we compare the two execution times of the simple and binary searches, we will notice that with small numbers the simple search can have faster results, but to what extent?

To find out, let's run some tests.

Comparatives

Now, let's use a book of 50,000 pages and the chosen page will be a random one.

Binary Search Basic Search

Random page in a 500,000 page book

*here we already start to notice a difference

Binary Search Basic Search

Random page in a 5,000,000 page book

*big time difference

Binary Search Basic Search

Final thoughts

Binary search is one of the strategies you can adopt when you need to look for something specific in a huge collection of other objects.

Even in everyday situations the use of binary search makes a lot of sense.

But the following observation is also important: if you are a beginner and you are having your first contact with BigO optimizations and performative operations, it is important that you know that binary search is NOT a silver bullet

It takes a while since it makes sense to use binary search instead of a basic search, and most likely your backend projects won't need it, as many frameworks you use already do.

Beware of overengineering.


Thumbnail by Takashi Miyazakion Unsplash.

Top comments (3)

Collapse
 
sjmulder profile image
Sijmen J. Mulder

For large lists the difference really is massive. I implemented the linear scan from your post, the binary search from your post, and the branchless binary search from mhdm.dev/posts/sb_lower_bound/ and when searching a list of 500 million for page 490 ish million, the linear search takes 0.85 seconds while the binary searches take 4 and 1 micro(!) seconds respectively.

Collapse
 
yelldutz profile image
Igor Duca

great! thank you for taking a time to test the code and read the article

Collapse
 
sjmulder profile image
Sijmen J. Mulder

Cheers! Forgot to mention btw that I reimplemented in C but I think that's only relevant for the branchless version.