Javascript Linear and Binary Search

If there is something you can not escape in programming is searching through data and there is many away to ask your computer to look into the memory for the precious data but behind the scene the process is not the same.

Linear Search

Linear search (or sequential search ) is the way to check each element one by one of the list until a match is found or the whole list has been searched.

Linear search will check each element one by one

It’s pretty simple and it’s the most common way to check each items by using a a loop. The javascript methods like indexOf, includes or find are linear search.

Best-case performance: O(1) (if it’s the first element)

Worst-case performance: O(n)

function linearSearch(arr, val){
    for(let i = 0; i < arr.length; i++){
        if(arr[i] === val) return i;
    }
    return -1;
}

Note! if you are using a method like indexOf, includes inside a loop the time complexity will be O(n2).

function linearSearch(arr, val){
    for(let i = 0; i < arr.length; i++){
        console.log(arr.indexOf(arr[i]))
    }
    
}

Binary Search

Rather than eliminating on element at the time, you can eliminate half the remaining elements at the time and it can be must faster however it only works on sorted elements.

Split up the array in the middle and check if it is in the left side or right side and repeat the process

Implementing the binary search:

• Start from the value in the middle of the array and compare this with the item.
• If the item is equivalent to the value of middle, return middle
• If the is less than the item of middle, recalculate middle such that it is increased
• If the item is greater than the value of middle, recalculate middle such that it is decreased
• Continue this while there is still an item to search for, or return null

const binarySearch = (arr, item) => {
 let left = 0;
 let right = arr.length - 1;
 let mid;
 
 while (left <= right) {
   mid = Math.floor((left + right) / 2);
  
   if (arr[mid] === item) return mid;
   if (arr[mid] < item) left = mid + 1
   else right = mid - 1;
 }
 return null;
}

Best-case performance: O(1) (if the first element match directly).

Worst-case performance: O(logN).

Space complexity : O(1).