Logarithmic

Logarithmic time means the work grows very slowly because the problem is cut down on every step. Binary search is the standard example: each comparison removes half of the remaining values.

function binarySearch(sorted, target) {
  let low = 0;
  let high = sorted.length - 1;
  while (low <= high) {
    const middle = Math.floor((low + high) / 2);
    if (sorted[middle] === target) return middle;
    if (sorted[middle] < target) low = middle + 1;
    else high = middle - 1;
  }
  return -1;
}

An input of 1,024 needs at most 10 comparisons. An input of 1,048,576 needs at most 20. That is the power of O(log n).

The catch is that binary search needs sorted data. The sort itself costs more than the search, so use it when the data is already ordered or searched many times.