What are Binary Search Algorithms?
For the first week in this new year, one of the most relevant algorithms I’ve been working on is the binary search algorithm. Binary search is such a useful type of algorithm since it efficiently makes things easier to find and is not too complicated to understand. Looked at in another way, it’s sort of like chopping a log over and over again in half until you reach the point you’d like to be at in the chopping. Specifically in the case of binary search, that desired point would be at the point of our target number.
What is binary search anyways?
Binary search means that in a group of sorted ordered things, maybe an array of numbers, the middle of that group is compared to the thing you are trying to search for (the target) to see if those two are a match. If they are a match, then you’ve found what you’ve been looking for, but if not then the sorted group is chopped in half and observed only on whatever side is applicable to how the middle compares to the target. For example if the thing you are looking for is greater in size than the middle value, then you should look on the right side since that is where the larger things are.
A quick example to implement this concept:
We are looking for the number 4 (target) in this list of 5 numbers in this array:
[1, 2, 3, 4, 5].
First you can look in the middle and see that 3 is the middle number. 3 is compared to 4 and 3 is smaller. So since these numbers are in order, it makes sense to look to the right of 3 to find the larger number, 4. 1 and 2 are eliminated and now 4 is the new middle of [3, 4, 5], which is equal to the target we are looking for.
Now for some coding. I will be going step by step into how I solved the binary search algorithm using JavaScript and as usual trying to simplify the process the best I can.
The Problem
Write a function that takes in a sorted array of integers as well as a target number and uses the binary search algorithm to find out if the target number is in the array. If it is, then the function should return the index of the target number. If it is not, then return -1.
The Solution
First using the keyword function, I’ve called our function the binarySearch function and given it the inputs listed above; an array and a target number. Additionally to use a binary search style of an algorithm, we’re going to need two pointers, namely a left and right one. These will be variables to represent indexes of each side of our array of numbers. The left will represent the first number and the right will represent the last number.
function binarySearch(array, target) { let left = 0
let right = array.length-1
At this point I will use a for loop as a way to look through all the numbers in our array to apply our logic. What comes next is initializing a middle variable which is assigned to using using Math.floor. Math.floor will round our results down to the largest integer less than or equal to what is in the parentheses. In the parentheses, we will be adding the left and the right pointer indexes together and dividing them by two to get the average, which will be in the approximate middle of our array.
function binarySearch(array, target) { let left = 0
let right = array.length-1 for (let i=0; i<array.length; i++){
let middle = Math.floor((left+right) / 2)
In this next phase, we will write an if statement which will check to see if the number in the middle of our array is the same as our target number. If it is, then we have found the number we are looking for so we will return the index of that number.
function binarySearch(array, target) { let left = 0
let right = array.length-1 for (let i=0; i<array.length; i++){
let middle = Math.floor((left+right) / 2)
if(array[middle] === target){
return array.indexOf(target)
If we have not found our target number we were searching for, then we have to go through our else if statements which are written below as a next step. Both of these are opposite to each other because we can have two possibilities at this point. Either the target we are looking for is smaller or larger than the number in the middle being compared to the target.
The first else if condition states that if the number in the middle is bigger than the target, then assign the right variable to the left side of the middle. This is where the “chopping” begins as we move the numbers we are now looking at over to the left side.
As stated earlier, the second else if condition is the exact opposite. If the target numbers is higher than the middle number then we need to assign the left variable to start from the first right space over the middle. The “chopping” would be to the right in this case.
function binarySearch(array, target) {let left = 0
let right = array.length-1
for (let i=0; i<array.length; i++){
let middle = Math.floor((left+right) / 2)
if(array[middle] === target){
return array.indexOf(target)
} else if (array[middle] > target){
right = middle-1
} else if (array[middle] < target){
left = middle +1
}
There is only one more possibility if none of our if conditions are being met. That would be that the number we are looking for does not exist in our array. If that’s the case, according to the problem statement, we would need to return -1 and close up our function, which is what is shown below.
function binarySearch(array, target) {let left = 0
let right = array.length-1
for (let i=0; i<array.length; i++){
let middle = Math.floor((left+right) / 2)
if(array[middle] === target){
return array.indexOf(target)
} else if (array[middle] > target){
right = middle-1
} else if (array[middle] < target){
left = middle +1
}
}
return -1
}
And this is the end of our algorithm. Understanding this algorithm is one of those things that I’ve found is key to understanding ones more difficult than this one. Binary search algorithms are one of the most fundamental concepts to really grasp while learning patterns of how data can be sorted to get to the results desired, so I encourage others to really take the time to understand it. Thanks for checking this guide out and I wish you a happy new year with new opportunities.
