Speed:

Binary Search

Time: O(log(n))Space: O(1)

💡How It Works

This search algorithm repeatedly reduces the search are by half on each iteration. Binary search only works on a sorted list. It repeats this process log₂(n) times when the target doesn't exist or if the target is the first or last element.

It's called "Binary" search because the algorithm repeatedly divides the search area into two (uses binary decision) at each step.

💻Implementation

function binarySearch(arr, target) {
  let high = arr.length;
  let low = 0;
  while (high >= low) {
    let mid = low + (high - low) / 2;
    if (arr[mid] === target) return mid;

    if (target > arr[mid])  low = mid + 1;
    else  high = mid - 1;
  }
  return -1;
}

🔍Deeper Look

Binary Search is a fast searching algorithm that works on a sorted array by repeatedly dividing the search space in half to locate a target value. Starting with the middle element, the algorithm compares this element with the target: if they match, the search ends; if the target is smaller, the search continues in the left half; if larger, in the right half. This halving process is repeated until the target is found or the search space is empty.

It is most suited for searching in large datasets instead of linear search.

🧪 Constrained but effective

Since binary search requires a sorted array, we may need to sort the dataset before searching. In exchange for some extra steps, it overtakes linear search by time taken. Perfect for large datasets.

🧙‍♂️ Variants in Practice

Binary Search is good for even large datasets but there exists variants like Ternery search which divides by 3 and Exponential Search which scans exponentially and uses binary search in a found range (useful for unbounded arrays).