Introduction
In my previous article Data Structures and Algorithms 101 you can read an introduction to what is data structures and algorithms.
In this article I will deep dive into Binary search algorithm. Searching algorithms falls into either sequential or interval search.Linear and binary searches are the commonly two simple as well as easy to implement algorithms.
Binary search is faster than linear search(where search is done in a sequence on every element). Here, am going to walk you through binary search algorithm and:
- define what is a binary search
- how to implement it
- where it can be used
What is binary search algorithm?
Binary search algorithm is a divide-and-conquer algorithm that divides elements in a sorted array roughly into half every time it checks for the target element we are searching.Simply put,we divide the problem into simpler problems until it becomes simple enough to solve them directly.
How do we implement a binary search?
You can implement most of the algorithms in two ways:
- Iteratively or
- Recursively
Iterative version of the algorithm involves a loop which repeats some steps until the stopping condition is met whereas recursive version uses a function that calls itself. I will be covering iterative version in this article.
We begin by implementing a function in JavaScript that search element value and returns its index:
const binarySearch = (elements, value) => {
// Add other code
}
Assuming we have a sorted array,set the lower(startIndex) and upper(endIndex) boundaries at the appropriate ends of the sequence:
const arr = [0,5,12,23,34,35,46,47,58];
const binarySearch = (elements,value) => {
let startIndex = 0;
let endIndex = arr.length - 1;
}
Now we will identity the middle element to see if it has the value we want to search.We calculate this middle value (middleIndex) by taking the average of both boundaries:
let middleIndex = Math.floor((startIndex + endIndex) / 2 );
Here, you notice I have used the Math.floor() function to help handle an odd and even number of element in the bounded range by flooring the result.
Now,we compare that middle element with the value we are looking for as a key:
- When the key is less than the middle element,we search in the left half
- when the key is more than the middle element,we search in the right half
- However,when the key is equal to the middle element,our search target is found and we return the index of the middle element.
Let us update our code to reflect the above steps:
const arr = [0,5,12,23,34,35,46,47,58];
const binarySearch = (elements,value) => {
let startIndex = 0;
let endIndex = arr.length - 1;
let middleIndex = Math.floor((startIndex + endIndex) / 2 );
if (elements[middleIndex] === value) {
return `Target value ${value} was found at index ${middleIndex}`;
} else if (elements[middleIndex] < value) {
startIndex = middleIndex + 1;
} else {
endIndex = middleIndex - 1;
}
}
To keep going,you enclose the above steps in a loop which will stop when the lower(startIndex) boundary overtakes the upper(endIndex) one.This can easily be achieved by adding a while loop our code as below:
const arr = [0,5,12,23,34,35,46,47,58];
const binarySearch = (elements,value) => {
let startIndex = 0;
let endIndex = arr.length - 1;
while (startIndex <= endIndex) {
let middleIndex = Math.floor((startIndex + endIndex) / 2 );
if (elements[middleIndex] === value) {
return `Target value ${value} was found at index ${middleIndex}`;
} else if (elements[middleIndex] < value) {
startIndex = middleIndex + 1;
} else {
endIndex = middleIndex - 1;
}
}
}
In other words,you can iterate as long as the lower boundary is below or equal to the upper one.Otherwise,there was no match found and the function returns undefined implicitly(lam returning a message informing the user that there was no match found in our array). Our code should now look as below:
'use strict'
const arr = [0,5,12,23,34,35,46,47,58];
const binarySearch = (elements,value) => {
let startIndex = 0;
let endIndex = arr.length - 1;
while (startIndex <= endIndex) {
let middleIndex = Math.floor((startIndex + endIndex) / 2);
if(elements[middleIndex] === value) {
return `Target value ${value} was found at index ${middleIndex}`;
}else if(elements[middleIndex] < value) {
startIndex = middleIndex + 1;
}else {
endIndex = middleIndex - 1;
}
}
return `Target value ${value} was not found in [${elements}]`;
}
console.log(`Result of binary search results: ${binarySearch(arr,35)}`);
To ensure your array is always sorted,add the following code:
let sortedArr = arr.sort((a,b) => {
return a - b;
});
With this addition our code should look as below:
'use strict'
const arr = [0,5,12,23,34,35,46,47,58];
const binarySearch = (elements,value) => {
let startIndex = 0;
let endIndex = arr.length - 1;
while (startIndex <= endIndex) {
let middleIndex = Math.floor((startIndex + endIndex) / 2);
if(elements[middleIndex] === value) {
return `Target value ${value} was found at index ${middleIndex}`;
}else if(elements[middleIndex] < value) {
startIndex = middleIndex + 1;
}else {
endIndex = middleIndex - 1;
}
}
return `Target value ${value} was not found in [${elements}]`;
}
let sortedArr = arr.sort((a,b) => {
return a - b;
});
console.log(`Result of binary search results: ${binarySearch(sortedArr,35)}`);
Sample iteration simulation from our binary search function
Where we can use binary search algorithm
Unlike other search algorithms, binary search can be used beyond just searching. For example, it allows for set membership testing, finding the largest or smallest value, finding the nearest neighbor of the target value, performing range queries, and more.
The Efficiency of Binary Search
The time complexity of the Binary Search is O(log2n), where n is the number of elements in the array. This is far better compared to the Linear Search, which is of time complexity O(n). Like many other search algorithms, Binary Search is an in-place algorithm. That means that it works directly on the original array without making any copies.
We have to keep in mind however, that Binary Search only works on sorted arrays. The sorting step itself, if using an efficient sorting algorithm, has a complexity of O(nlogn). This means that in most cases, if the array is small, or if we need to search it only once, a brute-force (e.g. Linear Search) algorithm might be better.
Given this, Binary Search really shines when we need to make repeated searches on large arrays. As previously mentioned, we needed only 3 comparisons (comparisons being the most intensive tasks of all search algorithms), for my array of 8 elements. However, if we had an array of 10,000,000 elements, we would only need to check 24 elements, i.e. 0.0002%_ of the entire array.
Conclusion
In this article, we have taken a look at Binary Search. It's simple, intuitive and efficient logic and implementation make it a very popular algorithm to demonstrate the divide-and-conquer strategy. Your feedback(s) are highly welcome and shall help me improve on this article or extend my understanding of algorithms.
Top comments (0)