Home>Javascript
popular search algorithms in js

Popular Search Algorithms in JS

•9 min read

On This Page

Search algorithms are some of the most essential elements in programming. They enable fast finding of a given element within data structures. This article explains the most widely used search algorithms using simple JavaScript examples.

Complexity

The types of searches are classified based on their complexity in terms of time and space, which may form subsets. An algorithm's time to run in terms of the input size is termed time complexity, while the space an algorithm occupies to run is termed space complexity.

We will be focusing on time complexity in this guide.

Time Complexity and Big O Notation

Big O Notation analyzes an algorithm by concentrating on the worst-case scenario.

For instance, O(n) is interpreted as the growth of execution time proportional to the input size.

Linear/sequential search is the simplest of all search algorithms, but is very important. It scans through each of the entries of the array or list and when it gets to the final element or it found the target element in the list.

To begin, the place- value of the first element is compared to the target value, then the second element and so on. If the element is found, it returns its index; else, it returns -1.

Time complexity: O(n), where n is the number of elements in the array.

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


const array = [3, 5, 7, 9, 11]
const target = 7
console.log(linearSearch(array, target)) // Output: 2

Binary search is preferably implemented in use cases where the data is sorted, and fast search is important. This applies the technique that consists in dividing the search interval in halves again and again. Binary search takes less time as compared to linear search but it uses a sorted array. Everytime it halves the list so that it searches for the target in the shorter list of the total lists. Then, the algorithm verifies the middle element of the array. If the target is equal to the integer of the middle element, then it succeeds. If the target is less than the middle element, the search continues on the left half, whereas if the target is greater than the middle element, the search continues on the right half.

Time Complexity: O(logn), where n is the number of elements in the array.

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


const sortedArray = [2, 4, 6, 8, 10]
const target = 6
console.log(binarySearch(sortedArray, target)) // Output: 2

Jump Search is the algorithm for searching for the element in the sorted array of the given list. It is better than the linear search, which uses a “jump” strategy that reduces the number of comparisons. The concept lies in dividing an array into a few sets of equal intervals and searching for an element in these created sets following a straight-line motion. The block size is always preferred to be the square root of the total number of elements in the array. Jump search is advantageous in large-scale sorted arrangements because it reduces the search scale relative to linear search when the array's length is considerable.

Jump Steps: Decide on some block size, preferably the square root of the size of the array (blockSize = Math.round(Math.sqrt(n)), where n is the size of the array).

Jump Forward: Beginning at the first element of the array, move forward by the block size until the block that contains the element is reached or until an element greater than the target is encountered. Linear Search Within the Block: Once the block of elements with the potential location of the target element is located, conduct a linear search within it to locate it precisely.

Return the Index: If the element is found, return its index; otherwise, return -1 to show that it doesn’t exist.

Time Complexity: O(√n​)O(n), where n is the number of elements in the array.

function jumpSearch(arr, target) {
  const n = arr.length
  const blockSize = Math.floor(Math.sqrt(n))
  let prev = 0
  // Jump forward in blocks
  while (arr[Math.min(blockSize, n) - 1] < target) {
    prev = blockSize
    blockSize += Math.floor(Math.sqrt(n))
    if (prev >= n) {
      return -1 // Target is not present in the array
    }
  }
  // Linear search within the identified block
  for (let i = prev; i < Math.min(blockSize, n); i++) {
    if (arr[i] === target) {
      return i // Target found, return the index
    }
  }
  return -1 // Target is not found
}


const sortedArray = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21]
const target = 15
const index = jumpSearch(sortedArray, target)
console.log(index) // Output: 7

Interpolation search is an extension of binary search; it is most efficient when the sorted array is uniformly distributed. The algorithm assumes the position of the target value based on the values at the extremes of the search interval and searches for it.

Time Complexity: O(loglogn) on average, O(n) in the worst case, where n is the number of elements in the array.

function interpolationSearch(arr, target) {
  let low = 0
  let high = arr.length - 1
  while (low <= high && target >= arr[low] && target <= arr[high]) {
    if (low === high) {
      if (arr[low] === target) return low
      return -1
    }
    const pos = low + Math.floor(((target - arr[low]) * (high - low)) / (arr[high] - arr[low]))
    if (arr[pos] === target) {
      return pos
    }
    if (arr[pos] < target) {
      low = pos + 1
    } else {
      high = pos - 1
    }
  }
  return -1
}


const uniformArray = [10, 20, 30, 40, 50, 60]
const target = 40
console.log(interpolationSearch(uniformArray, target)) // Output: 3

It is a search algorithm used to search for elements in presorted arrays. This is done in a manner that the search range is doubled the previous range (1, 2, 4, 8, and so on) until the range is identified within which the target element may be present.

After the range is identified, a binary search is conducted within it, where the actual search for the target is conducted.

This approach uses hand speed in range identification and the needle in the haystack type of the binary search method, particularly the latter, which will be used for large sorted sets of data.

Time Complexity: O(log⁡n)

function exponentialSearch(arr, target) {
  if (arr[0] === target) return 0


  let i = 1
  while (i < arr.length && arr[i] <= target) {
    i *= 2
  }


  return binarySearch(arr, target, Math.floor(i / 2), Math.min(i, arr.length))


  function binarySearch(arr, target, left, right) {
    while (left <= right) {
      const mid = Math.floor((left + right) / 2)
      if (arr[mid] === target) {
        return mid
      } else if (arr[mid] < target) {
        left = mid + 1
      } else {
        right = mid - 1
      }
    }
    return -1 // Target not found
  }
}


const arr = [1, 2, 4, 8, 16, 32, 64, 128]
const index = exponentialSearch(arr, 32) // Output: 5
console.log(index)

Depth-First Search (DFS)

Depth-First Search (DFS) is used primarily for traversing or searching tree and graph data structures. It explores as far down a branch as possible before backtracking. DFS starts at a given node and explores each branch as far as possible before backtracking to explore other branches. It can be implemented using recursion or a stack.

Time Complexity: O(V+E), where VVV is the number of vertices, and EEE is the number of edges.

function dfs(graph, start, visited = new Set()) {
  console.log(start) // Process the current node
  visited.add(start)


  for (const neighbor of graph[start]) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited) // Recursively visit unvisited neighbors
    }
  }
}


const graph = {
  A: ['B', 'C'],
  B: ['D', 'E'],
  C: ['F'],
  D: [],
  E: ['F'],
  F: [],
}


dfs(graph, 'A') // Output: A B D E F C

Breadth-First Search (BFS)

Breadth-First Search (BFS) is also used to traverse or search tree and graph structures. It explores all neighbors at the present depth before moving on to nodes at the next depth level. BFS starts at the root (or any arbitrary node) and explores all its neighbors before moving to the next level of neighbors. It is usually implemented with a queue.

Time Complexity: O(V+E), where V is the number of vertices and E is the number of edges.

function bfs(graph, start) {
  const queue = [start]
  const visited = new Set()
  visited.add(start)
  while (queue.length > 0) {
    const node = queue.shift() // Dequeue a node
    console.log(node) // Process the current node
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor)
        queue.push(neighbor) // Enqueue unvisited neighbors
      }
    }
  }
}


const graph = {
  A: ['B', 'C'],
  B: ['D', 'E'],
  C: ['F'],
  D: [],
  E: ['F'],
  F: [],
}


bfs(graph, 'A') // Output: A B C D E F

Conclusion

These search algorithms are essential for various programming situations. Linear search is relatively straightforward but not very efficient if one has a large number of records to search from. On the other hand, binary search is much more efficient than the other, but the data must be sorted. DFS and BFS are supposed to traverse complex structures like graphs. Interpolation is very useful for uniformly distributed data.

Therefore, we can write optimized JavaScript code by knowing when and when not to use these algorithms.

Read Next

Codevertiser Magazine

Subscribe for a regular dose of coding challenges and insightful articles, delivered straight to your inbox