The core concept of data structures and algorithms are essential in the field of programming. These algorithms are an essential part of any tools that we use during the development of any product. It helps improve the overall performance and efficiency of our product as a whole. So, understanding of data structures and algorithms can make you a better and efficient programmer. Here, we are going to learn one of the basic and efficient search algorithms i.e. Binary Search Algorithm and exemplify it using JavaScript program.
What is Binary Search?
Binary Search is the search technique which is used to locate a particular item in a sorted list.
Remember that the list must be sorted.
If the list is unsorted then the algorithm will not be able to produce the expected result. The concept of this search is similar to Binary Search trees.
This technique works on Divide and Conquer approach.
The time complexity of this search technique is O(logn) which is way faster than the linear searching technique which has the complexity of O(n).
This searching technique repeatedly divides the array or list into half and performs the search.
It works by checking if our search value is less than, more than or equal to the middle value in our array.
The algorithm is simple:
- First, if the search value is less than the middle value of our list, we remove the right half of the array.
- Second, if the search value is more than the middle value of our list, we can remove the right half of the array.
- Finally, if the search value is equal to the middle value of our list, we return the value.
See, not hard to understand at all!
Now, you must have figured out why the list must be sorted before performing Binary Search. It is so that we can appropriately divide the list into half to search for our item by removing the half that does not concern. This effectively makes the algorithm faster as half of the list is removed.
Now, let’s implement the Binary Search technique in JavaScript programming language.
Implementation in JavaScript
The idea is simple.
Initialize the start index to 0 and then end index to list-1. Locate the mid-value by adding start and end index and dividing it by 2. If the item we are searching is equal to mid-value then return true as we have found the item. If the item is greater than the mid-value then initialize start index as one greater than mid-value i.e. mid + 1 else if the item is smaller than mid-value initialize the end index as one less than mid-value i.e. end — 1. This will remove the half the array each time until only mid-value is available and then if it’s equal to the item then return true else false.
The code to implement Binary Search in JavaScript is given below:
let BinarySearch = function (list, item) {
let startIndex = 0,
let endIndex = (list.length)-1;
while (startIndex <= endIndex ){
// Find the mid-value
let midValue = Math.floor((startIndex + endIndex)/2);
// If searched item is located at mid, then return true
if (list[midValue]===item){
return true;
}
// Else divide the array into left and right half
else if (list[midValue] < item){
startIndex = midValue + 1;
}
else{
endIndex = midValue - 1;
}
}
return false;
}
let list = [1, 5, 7, 9 ,10, 12, 14, 20];
let item = 7;
if (BinarySearch(list, item)){
document.write("Item has been found!!");
}
else {
document.write("Item not found!!!");
}
Output:
Item has been found!!
Conclusion
This article defines what Binary Search Technique is and its implementation in JavaScript. The binary search algorithm is simple and easy to implement. Its search efficiency is greater than that of the linear search technique. The time complexity is much faster. This technique is one of the essential parts of the data structure and algorithm that programmers must know in order to provide more efficient and fast working codes.
Originally published at https://kriss.io on August 22, 2019.
Top comments (0)