Common Searching Algorithms in JavaScript

I am currently a few weeks post-coding bootcamp and am beginning to navigate the world of technical interviews. With that comes a necessary deep dive into data structures and algorithms. In the interest of using teaching as a learning tool, I will be documenting my learning process here.

Let's begin with Searching Algorithms!

Linear Search

Linear search is a common searching algorithm that accepts an array and a value - and returns the index at which that value exists. If that value does not exist, the function will return -1. To implement:

1. Begin with a for loop that starts at i and iterates through the length of the array
2. Check if the current array element is equal to the given value.
3. If found, return the index of that value
4. If the value does not exist, return -1 The code is as follows:

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

The average and worst time complexity for this function is O(N) and the best case time complexity is O(1). Our next searching algorithm will improve upon this time complexity.

Binary Search

Binary search is an algorithm that can be MUCH more efficient than linear search, with the caveat that it only works on sorted arrays. To implement:

1. Create a function that accepts a sorted array and a value.
2. Create a left pointer at the start of the array and a right pointer at the end of the array.
3. While the left pointer is in front of the right pointer:
   • Create a pointer in the middle of the array. You can find this middle value by taking the average of your start and end values and using Math.floor() to ensure a rounded number
   • If you find your matching value, return the index
   • If the value is too small, move the left pointer up
   • If the value is too large, move the right pointer down
   • Continue this process until you find the correct value
4. If the value is not present, return -1

The code is as follows:

function binarySearch(arr, elem) {
    let start = 0;
    let end = arr.length - 1;
    let middle = Math.floor((start + end) / 2);
    while(arr[middle] !== elem && start <= end) {
        if(elem < arr[middle]) end = middle - 1;
        else start = middle + 1;
        middle = Math.floor((start + end) / 2);
    }
    return arr[middle] === elem ? middle : -1;
}

Remember! This method only works on sorted arrays! However, if you do have a sorted array, the time complexity is improved greatly when compared to linear search. The worst and average time complexity is O(log n) and the best case is O(1).

Naive String Search

The final searching algorithm I will be covering is naive string search. This algorithm is useful for finding patterns within larger strings. For instance, you could try to find how many times "AABA" appears in the string "AABAACAADAABAABA". To implement:

1. Define a function that takes a larger string and then the string that contains the pattern you are looking for
2. Loop over the longer string
3. Within that loop, loop over the shorter/pattern string
4. Check for a match
   • If you find a match, keep going
   • If you find a complete match, increment your match count
5. If no match is found, break out of the inner loop
6. Return the total count at the end

The code is as follows:

function naiveSearch(long, short){
  let count = 0;
  for(let i = 0; i < long.length; i++){
    for(let j = 0; j < short.length; j++){
      if(short[j] !== long[i+j]) break;
      if(j === short.length - 1) count++;
      }
    }
 return count;
}

The best case time complexity for naive string search is O(n). The worst case is O(m*(n-m+1)). This author discusses this unique time complexity further.

This has been my quick guide to basic searching algorithms in JavaScript. I am still learning this material and welcome comments and critiques!

Sources

1. For more detailed information, checkout this Udemy course I am currently taking! JavaScript Algorithms and Data Structures Masterclass
2. The Naive String Matching Algorithm
3. Naive Algorithm for Pattern Searching