Notes on Algorithms 1, Binary Search

Algorithms are recipes to come up with a solution. Large algorithms are actually a collection of lots of smaller algorithms. When it comes to working with lots of data, making an efficient algorithm becomes important. The study of algorithms is needed to build big systems. This could result in the saving of computer time which translates into money saved.

There are bunch of popular algorithms in the computer science land. Since computers like to work with a lot of data, it makes sense to come up with better ways to sort and search all these data. Data structures and algorithms go hand in hand together.

One such searching algorithm is the binary search algorithm. Given a list of already sorted items, It will keep splitting the list in half until it finds the item it was looking for.


Photo by rawpixel.com from Pexels

Let’s say I am thinking a number between 1 and 16. (the number is 7)

Let’s divide the list in 2 and come up with a round number. The computer came up with a guess of 8.

Is your number 8?

No, my number is lower.

Okay, since the number is lower than the guess, the algo will eliminate all the numbers from 9-16. Since 8 is higher than the guess, that means 8 is not the number, so it will be eliminated also. Now the shortened list is 1-7.

Repeat the process to find 4. Was it 4 that you guessed?

No, but it’s higher.

Oh, let me eliminate all numbers which were lower than 4, and also removing 4 because it’s not the number. Now the remaining numbers are 5, 6, 7.

My new guess is 6..

Repeat the process to come up with 7. Was the number you were guessing was 7?

YES!!

Within just 4 guesses I got the number.

Compared to linear search which will go like this:

Is your number 1?
NO
Is your number 2?
NO
Is your number 3?
NO

Is your number 7?
YES!

There is a formula to find how many tries will it take to make the search. It’s: log2(n)

2^4 = 16. It will take the 4 + 1, or up to 5 guesses to come up with the number.

  • 2^1 = 2
  • 2^2 = 4
  • 2^3 = 8
  • 2^4 = 16
  • 2^5 = 32
  • 2^6 = 64
  • 2^7 = 128
  • 2^8 = 256
  • 2^9 = 512
  • 2^10 = 1024

Let’s say I have a list of 312 items. How many tries will it take for a binary search algorithm to find the given item?

log2(312) = ?

The closest power is 2^8 = 256. That means it will take 8 + 1 or at most 9 tries to find an item within a list of 312 items.

See binary search implemented in JavaScript.

Leave a Reply

Your email address will not be published. Required fields are marked *