Binary Search & The Two-Pointer Pattern

Dividing sorted search spaces in O(log n) and sliding window algorithms

« Hash Tables & Hash Maps: O(1) Lookups« Previous Sorting Algorithms: QuickSort & MergeSort »Next »

Binary Search finds the position of a target value within a sorted array by repeatedly dividing the search space in half, achieving O(log n) time complexity.

The Binary Search Loop

Prerequisite: The array MUST already be sorted!

Maintain low and high pointers. Calculate mid = low + Math.floor((high - low) / 2).

If arr[mid] === target, return index. If arr[mid] < target, discard left half (low = mid + 1). Otherwise discard right half (high = mid - 1).

Standard Iterative Binary Search

Try It Yourself »

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

  while (low <= high) {
    // Avoid integer overflow bug in large systems
    const mid = Math.floor(low + (high - low) / 2);

    if (arr[mid] === target) {
      return mid; // Found target at index mid
    } else if (arr[mid] < target) {
      low = mid + 1; // Target is in the right half
    } else {
      high = mid - 1; // Target is in the left half
    }
  }

  return -1; // Target not found
}

const primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
console.log(binarySearch(primes, 13)); // 5

Searches 10 items in <= 4 comparisons.

Google AdSense Slot (inContentBanner)

Set your Publisher ID in src/config/ads.ts to display live ads.

Test Yourself With Exercise

+15 XP

What is the absolute prerequisite condition that an array must satisfy before Binary Search can be applied?

« Previous: Hash Tables & Hash Maps: O(1) Lookups Next: Sorting Algorithms: QuickSort & MergeSort »