Implementing Binary Search in JavaScript with Logarithmic Complexity

Scanning an array element by element with Array.prototype.indexOf or find requires O(n) linear time—meaning an array of one million items can take up to one million comparisons in the worst case. When your dataset is already sorted, Binary Search exploits that ordering by comparing the target value against the middle element and eliminating half of the remaining search space on every step.

Because the search interval is halved on each iteration, Binary Search runs in O(log n) logarithmic time: searching 1,048,576 sorted elements takes at most 20 comparisons.

Example #

const sortedPrices = [12, 24, 35, 48, 60, 75, 89, 104, 120];

binarySearchIterative(sortedPrices, 75);
// Output: 5 (index of 75)

binarySearchIterative(sortedPrices, 50);
// Output: -1 (not found)

Input : Sorted numeric array and a target number
Output : Zero-based index of the target element, or -1 if the value does not exist in the array.

Implementation #

/**
 * Iterative Binary Search
 * Time Complexity: O(log n)
 * Space Complexity: O(1)
 */
function binarySearchIterative(sortedArray, target) {
  let left = 0;
  let right = sortedArray.length - 1;

  while (left <= right) {
    // Avoid potential overflow in languages with fixed-width integers
    const mid = left + Math.floor((right - left) / 2);
    const current = sortedArray[mid];

    if (current === target) {
      return mid;
    }

    if (current < target) {
      // Target is in the upper half
      left = mid + 1;
    } else {
      // Target is in the lower half
      right = mid - 1;
    }
  }

  return -1;
}

/**
 * Recursive Binary Search
 * Time Complexity: O(log n)
 * Space Complexity: O(log n) call stack frames
 */
function binarySearchRecursive(
  sortedArray,
  target,
  left = 0,
  right = sortedArray.length - 1
) {
  if (left > right) {
    return -1;
  }

  const mid = left + Math.floor((right - left) / 2);
  const current = sortedArray[mid];

  if (current === target) {
    return mid;
  }

  if (current < target) {
    return binarySearchRecursive(sortedArray, target, mid + 1, right);
  }

  return binarySearchRecursive(sortedArray, target, left, mid - 1);
}

Main Point: Prefer the iterative while (left <= right) Binary Search in production JavaScript because it achieves the same O(log n) time complexity as recursion while maintaining O(1) constant memory overhead.

Credits #

Photo by safar safarov

← Home