What are Linear and Binary search in Javascript?
Yong Liang
Posted on June 18, 2019
How do Linear Search & Binary Search work?
A linear search checks each items in a collection of data one at a time in order to find the searching item. For example, when we search an item in an array, the worse case is that we have to literate through the whole array, which gives us an O(n) performance. An example of linear search would look like this in Javascript:
//Linear Search
let arr = [1,4,3,9,5,2,7,8]
//this function accepts an array and an element to be searched
function linearSearchArray(arr, targetElement){
for(let eachItemIndex in arr){
if(arr[eachItemIndex] === targetElement){
return eachItemIndex;
}
}
return -1;
}
linearSearchArray(arr, 9) //will return 3 because 9 has an index of 3 in the array.
Binary Search
A binary search is a little more complicated and only works on a sorted array. Binary search in a nutshell is that we first look at the middle element in a sorted array, then compare it with the item we are searching for, if the middle element is greater than the searching item, then we know that half of the elements in the array are greater than the item we are searching for, therefore we can drop that half of the array and search only the other half. We continue this operation until we find the element we are looking for.
In a worse case, as we shrink the array, eventually there will be only one element left to check, if that isn't the matching element then the element we are looking for is not in the array. Because we drop half of the array each time we check, the size of the array is divided by 2 every time we conduct a comparison. Hence the time complexity of a binary search is O(log n). It is much faster than linear search on average. Here is one way to implement a binary search in Javascript:
//Binary Search
let arr = [1,4,3,9,5,2,7,8]
//this function takes an array and an element we want to find arguments
function binarySearchArray(arr, target){
//define the positions we will work with
let startPosition =0, endPosition = arr.length -1, midPosition = 0;
//use a while loop to keep dividing and looking for the target
while(startPosition <= endPosition){
//define and update the middle position
midPostion = Math.floor((startPosition + endPosition) /2);
//break the loop when target is equal to the middle element
//otherwise we update either the start or the end position so that half //of the array will be dropped.
if(target == arr[midPostion]){
console.log("target found at index:", midPostion);
return true;
}
else if(arr[midPostion] < target){
startPosition = midPostion +1;
//console.log("target not yet found");
}
else{
endPosition = midPostion -1;
//console.log("target not yet found");
}
}
return false;
}
//call the function
binarySearchArray(arr, 9)
//this returns target found at index: 3 true
Posted on June 18, 2019
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
