Computer Science 4 Newbies - Understanding Binary Search
Tags: backenddevelopment, typescript, algorithms
Published: 2023-08-14 00:04:06

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4rw7rax3old5cg9sbnjw.png)

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sxip0s2i6ftr2ad5jsfu.png)

### 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/aashghy8p8cgz5u41mm7.png)

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
:-------------------------:|:-------------------------:
![](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/f8q5e9n4sh3frtzvjo62.png)  |  ![](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/szehzyy659u2cv13g9ra.png)

Random page in a 500,000 page book

*here we already start to notice a difference

Binary Search              |  Basic Search
:-------------------------:|:-------------------------:
![](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ncfjau0ffx32o9umyju5.png)  |  ![](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5ac8pw65b84y5kou8igu.png)

Random page in a 5,000,000 page book

*big time difference

Binary Search              |  Basic Search
:-------------------------:|:-------------------------:
![](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2cghm8xs9jqghsimqk1j.png)  |  ![](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/eobsn3c4fioej4525v4g.png)

### 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](https://unsplash.com/photos/45gjufHdcKo).