DEV Community

Yong Liang
Yong Liang

Posted on

What are Linear and Binary search in Javascript?

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

Top comments (0)