Algorithms: Binary Search

Hey ya’ll…still breaking my brain with algorithms, this time it’s about Binary Search! A binary search is an advanced search algorithm that finds and retrieves data from a sorted list. Binary search compares the target value to the middle element of an array. The Binary search works by repeatedly dividing in half the portion of the list that may contain the element you are looking for until it’s narrowed down the possible options to just one.

Visual of how Binary search works.

The Binary search is similar to a guessing game like if you ask you friend to think of a number between 1 & 50. You have to try & guess what that number is and that number will only be between those two, you guess 85. Let’s say you choose 8, your friend says no higher, then you chose 45, friend says no lower. Now we can rule out 1,2,3,4,5,6,7,8,45,46,47,48,49,50. There’s no need to even think of those numbers. The window of numbers to choose from gets smaller. Let’s guess 20, friend say no higher, let’s do 30, friend says lower. We’re able to remove a big chunk of possible options and we know what those numbers are so we won’t think of them when guessing what the number is.

1. Let min = 1 and max = n.
2. Guess the average of max and min, rounded down so that it is an integer.
3. If you guessed the number, stop. You found it!
4. If the guess was too low, set min larger than the guess.
5. If the guess was too high, set max be one smaller than the guess.
6. Go back to step two.

Math.floor() function returns the largest integer less than or equal to a given number.