Searching Algorithms

Overview Table

Algorithm	Efficiency	Importance	Category	Strategy
Binary Search	★★★★★	★★★★★	Array Search	Divide and Conquer
Linear Search	★☆☆☆☆	★★★★☆	Array Search	Sequential
Depth-First Search (DFS)	★★★☆☆	★★★★★	Graph/Tree Search	Depth-First
Breadth-First Search (BFS)	★★★☆☆	★★★★★	Graph/Tree Search	Breadth-First
Interpolation Search	★★★★☆	★★★★☆	Array Search	Interpolation
Exponential Search	★★★★☆	★★★★☆	Array Search	Exponential
Jump Search	★★☆☆☆	★★★☆☆	Array Search	Jumping
Ternary Search	★★★★☆	★★☆☆☆	Array Search	Divide and Conquer
Fibonacci Search	★★★★☆	★★☆☆☆	Array Search	Fibonacci Sequence

Binary Search

Explanation: Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

Time Complexity: O(log(n))

History: The concept of binary search dates back to John Mauchly in 1946, and it was formally analyzed by Derrick Henry Lehmer in the early 1960s.

Visualizations:

Code Sample:

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let 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; // Element not found
}

const sortedArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(binarySearch(sortedArray, 7)); // Output: 6

tip

The while (left <= right) loop condition ensures that there is a valid search space to look for the target. For example if left = 3 and right = undefined, the loop will exit immediately as there is no valid search space.

Interpolation Search

Explanation: Interpolation search is an improvement over binary search for instances where the elements of the array are sorted and are uniformly distributed. It estimates the position of the target value within the array and adjusts the search interval based on the estimated position.

Time Complexity: O(log(log(n))) average, O(1) best case, O(n) worst case

History: Interpolation search was introduced by W. W. Peterson in 1957.

Visualizations:

Code Sample:

function interpolationSearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high && target >= arr[low] && target <= arr[high]) {
    // this is just checking if we have any variability in the array
    // EX: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] we can simply check for the target
    // or return early with a fail
    if (low === high) {
      if (arr[low] === target) return low;
      return -1;
    }

    // Estimate the position of the target value
    let 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; // Element not found
}

const sortedArray = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
console.log(interpolationSearch(sortedArray, 70)); // Output: 6

There are a couple of interesting parts to break down here:

• The conditions of the while loop
• The calculation of the pos variable

Conditions of the while Loop

The while loop in the interpolationSearch function has three conditions that need to be satisfied for the search to continue:

1. low <= high: This ensures that the search interval is valid and not empty.
2. target >= arr[low]: This checks if the target value is greater than or equal to the first element of the search interval. If the target is less than the first element, there is no need to continue the search.
3. target <= arr[high]: This checks if the target value is less than or equal to the last element of the search interval. If the target is greater than the last element, there is no need to continue the search.

Calculation of the pos Variable

The pos variable is calculated using the formula:

let pos =
  low +
  Math.floor(((target - arr[low]) * (high - low)) / (arr[high] - arr[low]));

This formula estimates the position of the target value within the array based on the value of the target, the first element of the search interval (arr[low]), and the last element of the search interval (arr[high]). The formula is derived from linear interpolation and is used to estimate the position of the target value within the array.

General equation of line : y = m*x + c.
y is the value in the array and x is its index.

Now putting value of lo,hi and x in the equation
arr[hi] = m*hi+c ----(1)
arr[lo] = m*lo+c ----(2)
x = m*pos + c     ----(3)

m = (arr[hi] - arr[lo] )/ (hi - lo)

subtracting eqxn (2) from (3)
x - arr[lo] = m * (pos - lo)
lo + (x - arr[lo])/m = pos
pos = lo + (x - arr[lo]) *(hi - lo)/(arr[hi] - arr[lo])

Linear Search

Explanation: Linear search is a simple search algorithm that checks each element in a list sequentially until the target element is found. It is inefficient for large lists but works well for small or unsorted lists.

Time Complexity: O(n)

History: Linear search is one of the simplest and earliest search algorithms used in computing and was formally described in early computer science literature.

Code Sample:

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

const array = [1, 3, 5, 7, 9];
console.log(linearSearch(array, 7)); // Output: 3

Exponential Search

Explanation: Exponential search involves two steps: finding the range where the target element could be using repeated doubling, and then performing a binary search within that range.

Time Complexity: O(log n)

History: The algorithm was introduced by Jon Bentley and Andrew Chi-Chih Yao in their 1976 paper "An Almost Optimal Algorithm for Unbounded Searching."

Code Sample:

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 - 1),
  );
}

function binarySearch(arr, target, left, right) {
  while (left <= right) {
    let 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; // Element not found
}

const sortedArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(exponentialSearch(sortedArray, 7)); // Output: 6

Explanation:

• The idea is to quickly find a range that we know the number is contained within to perform a binary search on that range.
• To find the range to perform the binary search, we start with an index i = 1 and keep doubling it until we find a value greater than the target or reach the end of the array.

The formulas for the left and right indexes that we put into the binary search are:

• left = Math.floor(i / 2)
• right = Math.min(i, arr.length - 1)

Because we just doubled i until we found a value greater than the target, we know that the target must be between i / 2 and i (or the end of the array if i is greater than the array length).

Jump Search

Explanation: Jump search works on sorted arrays by jumping ahead by fixed steps or blocks to find the block where the target element may reside, then performing a linear search within that block.

Time Complexity: O(√n)

History: Jump search was introduced by R. W. Floyd in 1964.

Code Sample:

function jumpSearch(arr, target) {
  const n = arr.length;
  const step = Math.floor(Math.sqrt(n));
  let prev = 0;

  while (arr[Math.min(step, n) - 1] < target) {
    prev = step;
    step += Math.floor(Math.sqrt(n));
    if (prev >= n) return -1;
  }

  while (arr[prev] < target) {
    prev++;
    if (prev === Math.min(step, n)) return -1;
  }

  if (arr[prev] === target) return prev;
  return -1; // Element not found
}

const sortedArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(jumpSearch(sortedArray, 7)); // Output: 7

Breadth-First Search (BFS)

Explanation: BFS is an algorithm for traversing or searching tree or graph data structures. It starts at the root (or an arbitrary node) and explores the neighbor nodes at the present depth before moving on to nodes at the next depth level.

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

History: The BFS algorithm was first described by computer scientists including Konrad Zuse in the 1940s and later popularized by Edsger Dijkstra in the 1950s.

Visualizations:

Code Sample:

Consider the following graph:

A -- B -- C
|    |
D -- E -- F

which can be represented with an adjacency list:

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

function bfs(graph, start) {
  const queue = [start];
  const visited = new Set();
  const result = [];

  while (queue.length) {
    const vertex = queue.shift();

    if (!visited.has(vertex)) {
      visited.add(vertex);
      result.push(vertex);

      for (const neighbor of graph[vertex]) {
        queue.push(neighbor);
      }
    }
  }

  return result;
}

bfs(graph, 'A'); // ['A', 'B', 'D', 'C', 'E', 'F']

or for a tree structure:

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

function createNode(value, left = null, right = null) {
  return {value, left, right};
}

const tree = createNode(
  1,
  createNode(2, createNode(4), createNode(5)),
  createNode(3, createNode(6), createNode(7)),
);

function bfs(node) {
  if (!node) {
    return [];
  }

  const queue = [node];
  const result = [];

  while (queue.length) {
    const current = queue.shift();
    result.push(current.value);

    if (current.left) {
      queue.push(current.left);
    }

    if (current.right) {
      queue.push(current.right);
    }
  }

  return result;
}

bfs(tree); // [1, 2, 3, 4, 5, 6, 7]

Depth-First Search (DFS)

Explanation: DFS is an algorithm for traversing or searching tree or graph data structures. It starts at the root (or an arbitrary node) and explores as far as possible along each branch before backtracking.

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

History: The DFS algorithm was first formally described by computer scientists including C. Y. Lee, who introduced the algorithm for maze-solving in 1961.

Visualizations:

Code Sample:

Consider the following graph:

A -- B -- C
|    |
D -- E -- F

which can be represented with an adjacency list:

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

function dfs(graph, start) {
  const stack = [start];
  const visited = new Set();
  const result = [];

  while (stack.length) {
    const vertex = stack.pop();

    if (!visited.has(vertex)) {
      visited.add(vertex);
      result.push(vertex);

      for (const neighbor of graph[vertex]) {
        stack.push(neighbor);
      }
    }
  }

  return result;
}

dfs(graph, 'A'); // ['A', 'D', 'E', 'F', 'B', 'C']

or for a tree structure:

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

function createNode(value, left = null, right = null) {
  return {value, left, right};
}

const tree = createNode(
  1,
  createNode(2, createNode(4), createNode(5)),
  createNode(3, createNode(6), createNode(7)),
);

function dfs(node) {
  if (!node) {
    return [];
  }

  const stack = [node];
  const result = [];

  while (stack.length > 0) {
    const current = stack.pop();
    result.push(current.value);

    if (current.right) {
      stack.push(current.right);
    }

    if (current.left) {
      stack.push(current.left);
    }
  }

  return result;
}

dfs(tree); // [1, 2, 4, 5, 3, 6, 7]

Comments

Recent Work

Basalt

basalt.software

Free desktop AI Chat client, designed for developers and businesses. Unlocks advanced model settings only available in the API. Includes quality of life features like custom syntax highlighting.

Learn More

BidBear

bidbear.io

Bidbear is a report automation tool. It downloads Amazon Seller and Advertising reports, daily, to a private database. It then merges and formats the data into beautiful, on demand, exportable performance reports.

Learn More