Learn what is binary search algorithm and how to implement it in javascript.
Binary search is the one of the most efficient and fastest search algorithm which searches the element in a sorted array. It searches the element in O(logn) or in the logarithmic time.
In comparison with linear search which searches the element in the given data set by checking all the elements, which results in O(n) time.
Binary search uses a divide and conquer approach and find the elements in the sorted data collection only.
How binary search works?
For binary search to work properly it is necessary that data collection is sorted in any order.
- It first gets the mid element from the data set and checks if the element that is need to be searched is this or not. If it is then return it else.
- If it is less, then it searches the element in the list from start till the mid element because it will be present there only.
- If it is greater than the mid element then it will search from mid to the last element.
- Repeat this till the element is found, if the element is not found then return -1.
As after each operation the length of the data set is reduced to half, that is why this algorithm is also known as half-interval search, logarithmic search, and/or binary chop.
Pseudo code for binary search
//Initially
//low = 0, high = dataset length
BinarySearch(A, value, low = 0, high = A.length - 1) {
if (high < low){
// value not found
return -1
}
//Get the mid
mid = (low + high) / 2
if (A[mid] > value){
//Search from start to mid
return BinarySearch(A, value, low, mid-1)
}else if (A[mid] < value){
//Search from mid to last.
return BinarySearch(A, value, mid+1, high)
}else{
return mid
}
}
Binary search in javascript.
As binary search uses divide and conquer technique it is quite to common to use recursive approach to implement it.
const binarySearch = (arr, value, low = 0, high = arr.length - 1) => {
//Search if the array exists
if(low <= high){
//Get the mid
const mid = Math.ceil((low + high) / 2);
//If element found
//Return its index
if(value === arr[mid]){
return mid;
}
//If value is less
//Then search in the lower range
if(value < arr[mid]){
return binarySearch(arr, value, low, mid - 1);
}else{
//Else search in greater range
return binarySearch(arr, value, mid + 1, high);
}
}
//If not found then return -1
return -1;
}
Input: const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; console.log(binarySearch(arr, 5)); console.log(binarySearch(arr, 11)); Output: 4 //Element 5 is found at index 4 -1 //Element does not exists in array
Time complexity: O(logn).
Space complexity: O(n) considering the call stack.
Performance of binary search in javascript.
Suppose we have to search for value 231232 in the array of 1 million element, then for linear search it would have taken O(n) in worst case which will result in O(1000000) opertaions.
But with binary search we can find the element in 20 iterations only. Here is the code of binary code which keeps the count of number of time the function is called.
const binarySearch = (arr, value, low = 0, high = arr.length - 1, count = 1) => {
//Search if the array exists
if(low <= high){
//Print the no of types function is called
console.log(count++);
//Get the mid
const mid = Math.ceil((low + high) / 2);
//If element found
//Return its index
if(value === arr[mid]){
return mid;
}
//If value is less
//Then search in the lower range
if(value < arr[mid]){
return binarySearch(arr, value, low, mid - 1, count);
}else{
//Else search in greater range
return binarySearch(arr, value, mid + 1, high, count);
}
}
//If not found then return -1
return -1;
}
//Input
let arr = [];
for(let i = 1; i <= 1000000; i++){
arr.push(i);
}
console.log(binarySearch(arr, 231232));
//Ouput
//20 //Took 20 calls to find
//231231 //Found at index
If you check the log2(1000000) it is 19.9315685693. As in the worst case we consider the upper limit, so we take the ceil value of it which is 20.
This shows that performance of binary search is much better than linear search.
That is why it is used to solve wide range of problems like finding the next-smallest or next-greater element in the sorted data collection.
Binary search tree and B-tree data structures are based on the binary search.
Duplicate elements
If the data set contains the duplicate elements then ideally it should return the first element from the collection, but binary search does not always returns the first element.
Input: const arr = [1, 2, 3, 4, 5, 5, 6, 6, 7, 8, 9, 10]; console.log(binarySearch(arr, 5)); console.log(binarySearch(arr, 6)); Output: 5 6
Element 5 is present at the 4th and 5th index but it returned 5. But for element 6 which is present at the 6th and 7th index it returned 6.
However many time it is necessary to find the leftmost or rightmost value from the collection which contains the duplicate values.
For this we will have to modify the binary search algorithm.
Find the leftmost value with the binary search.
While find the left most occurrence of the duplicate element in the array, even if we have found the element in the collection we have to keeping looking in the lower range to get the first occurrence.
const leftMost = (arr, value, low = 0, high = arr.length - 1, result = -1) => {
//Search if the array exists
if(low <= high) {
//Get the mid
const mid = Math.ceil((low+high) / 2);
//If element found
//Store the result
//And the check the lower range to make sure we get the first occurrence
if(value === arr[mid]){
result = mid;
return leftMost(arr, value, low, mid - 1, result);
}
//If value is less
//Then search in the lower range
if(value < arr[mid]){
return leftMost(arr, value, low, mid - 1, result);
}else{
//Else search in the upper range
return leftMost(arr, value, mid + 1, high, result);
}
}
//In the end return the result
return result;
}
Input: const arr = [1, 2, 3, 4, 5, 5, 6, 6, 7, 8, 9, 10]; console.log(leftMost(arr, 5)); console.log(leftMost(arr, 6)); Output: 4 //index of the first 5 in the array 6 //index of the first 6 in the array
Find the rightmost value with binary search.
For finding the rightmost value, even if we have found the element, we will have to keep checking in the upper range to get the last occurrence of the elements.
const rightMost = (arr, value, low = 0, high = arr.length - 1, result = -1) => {
//Search if the array exists
if(low <= high) {
//Get the mid
const mid = Math.ceil((low+high) / 2);
//If the element found
//Store the result
//And keep checking the upper range to get the last occurrence of element
if(value === arr[mid]){
result = mid;
return rightMost(arr, value, mid + 1, high, result);
}
//If value is less
//Then check in the lower range
if(value < arr[mid]){
return rightMost(arr, value, low, mid - 1, result);
}else{
//Else check in the upper range
return rightMost(arr, value, mid + 1, high, result);
}
}
//In the end return the result
return result;
}
Input: const arr = [1, 2, 3, 4, 5, 5, 6, 6, 7, 8, 9, 10]; console.log(rightMost(arr, 5)); console.log(rightMost(arr, 6)); Output: 5 //index of the last 5 in the array 7 //index of the last 6 in the array
Variations of binary search
Uniform binary search
It stores the difference between the current and the two next possible mid elements instead of start and end range.
Exponential search
It extends the binary search to the unbounded lists. It starts by finding the first element with an index that is both a power of two and greater than the target value. Afterwards, it sets that index as the upper bound, and switches to binary search.
Exponential search works on list that are bounded, but if the target value lies near the beginning of the collection, it becomes an improvement over the binary search.
Interpolation search
It estimates the position of the search value in the collection rather than calculating the midpoint by considering the lowest and highest elements in the array as well as the length of the array.
This works on the assumption that the midpoint is not the best guess in many cases. For example, if the search value is close to the lowest element in the array, then it is likely to be located near the start of the array.
Fractional cascading
To search the same element in the multiple sorted arrays with binary search will take O(klogn) where k is the number of sorted arrays.
But using fractional cascading we can do it in O(k + logn) by storing specific information in each array about each element and its position in the other arrays
Generalization to graphs
Binary search can be generalized to work on a certain types of graphs, where the search value is stored in a vertex rather than in an array element.
Binary search tree is the example of this, where a node(vertex) in the tree is queried, the algorithm learns that either the node(vertex) is the target, or otherwise which subtree the target would be located in.
Noisy binary search
Noisy binary search algorithms solve the case where the algorithm cannot reliably compare elements of the array.
For each pair of elements, there is a certain probability that the algorithm makes the wrong comparison. Noisy binary search can find the correct position of the target with a given probability that controls the reliability of the yielded position.
