Searching Algorithms: An quick recap

ยท

4 min read

We all would have been in a situation at least once where we were required to perform a search on a larger data set, either for work or while learning DSA. But now it might have been eons since you've encountered such tasks.

Let's take a quick recap of commonly used searching algorithms in the blog post.

Searching an unsorted data set

We are not equipped with much better options in this frontier. Linear search is the only search option available for searching on an unsorted data set.

Linear search works by iterating through all the elements in the data set one by one and checking if the current element matches the element we are looking for. Typically if a match is found then the index of the element in the data set is returned. If such searched element is not in the data set, then -1 is returned as the index.

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

linearSearch([5, 3, 43, 6, 23, 2, 4], 23) // returns 4
Time Complexity: O(n)
Space Complexity: O(1)

Searching a sorted data set

We all know that the word synonymous to searching a sorted dataset is a binary search. It can't get more efficient when it comes to searching a sorted dataset.

Binary search uses divide and search patterns to reduce the number of operations done rapidly. when a linear search's time complexity grows along with input linearly, binary search does the job in logarithmic time.

Since we know that the data set is sorted we can discard a lot of cases to match and focus on only there subset of the main dataset which could hold our searched element based on its position in ascending order.

function binarySearch(arr, key){
  let start = 0, end = arr.length - 1;
  while (start <= end) {
      let mid = Math.round((start + end) / 2);
      if (arr[mid] === key) return mid;
      else if (arr[mid] > key) end = mid - 1;
      else start = mid + 1;
  }
  return -1;
}

binarySearch([2, 6, 9, 14, 25, 56, 79, 112, 182), 112) // returns 7
Time Complexity: O(log n)
Space Complexity: O(1)

Searching substring on a larger string

Often, we would have encountered such scenarios in which we want to check if a given string is a substring of a given target string.

Naive searching is a simple but comparatively inefficient algorithm to do this. We start by iterating through all the elements in the target string and once we find a match to the first element of the substring we would start an inner loop that iterates through all the substring and check if it matched with the target string. If yes then it could be counted as a substring, else move the other loop iteration to the next index & repeat.

// search & count how times substring is present in the target string

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

naiveSearch('madening mad max is mad', 'mad') // returns 3
Time Complexity: O(m*n)
Space Complexity: O(1)

Knuth-Morris-Pratt Pattern matching algorithm

Naive search is ok, but as mentioned earlier it's inefficient. when we are searching a substring there might be cases where even after matching 90% of a substring in parent string, deviance could come. at this point, the native search will roll back all the progress and restart matching the pattern from the next iteration of the outer loop.

KMP Pattern matching algorithm comes up with an ingenious pattern matching solution that would be more efficient than naive search.

Unfortunately, it will take an entire blog post of itself. so will be covering that in the upcoming days.

I hope this quick read was helpful. more coming this way, so keep an eye out โœจ๐Ÿ˜Š.


Follow me on my socials to get an update on when I publish new blog posts. I also write some useful microblogs here.

Twitter: twitter.com/0xdeee
LinkedIn: linkedin.com/in/0xdeee
ย