Data Structures and Algorithms In-Depth
Module F-11·12 min read

O(log n) search and its variants — first/last occurrence, rotated arrays, and peak finding.

Written by Jatin Jain Saraf · Architect of SupraScan

Module F-11 — Binary Search and Its Variants

What this module covers: Every search technique so far in Foundation has been O(n) — a full scan, a two-pointer sweep, a sliding window. This module introduces the first O(log n) technique: binary search, which works whenever data is sorted (or has an equivalent monotonic property), and its variants — finding boundaries, searching rotated data, and finding a peak — that all reuse the same halving idea.

The Core Idea: Halving, Not Scanning

Binary search works on sorted data by repeatedly checking the middle element and discarding the half of the search space that can't contain the answer:

function binarySearch(sorted: number[], target: number): number {
  let left = 0;
  let right = sorted.length - 1;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2); // avoids overflow vs (left + right) / 2
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) left = mid + 1;  // target must be in the right half
    else right = mid - 1;                       // target must be in the left half
  }
 
  return -1; // not found
}

Each comparison eliminates half of whatever's left, not just one element. Starting from n elements, after one comparison there are n/2 candidates left, then n/4, then n/8 — the number of halvings needed to get down to a single candidate is log₂(n). At a million elements, that's roughly 20 comparisons — not a million, not even a thousand. This is the O(log n) complexity class from Module F-1's table, made concrete.

Analogy: Binary search is how you actually look up a name in a phone book (if you've ever seen one) or find a word in a physical dictionary — you don't start at page 1. You open to the middle, see you've overshot or undershot, and repeat on the correct half. Nobody scans a dictionary front to back.

The one hard requirement: the data must be sorted, or have some equivalent monotonic property (a "yes/no" answer that flips exactly once as you scan across the range) — binary search has no way to know which half to discard on unsorted data, because there's no guarantee about what's on either side of the midpoint.

Finding the First or Last Occurrence

Plain binary search finds a match, but stops as soon as it finds one — if the target appears multiple times, which one you get back is unspecified. Finding the first occurrence specifically requires a small but important tweak: don't stop on a match, keep searching left for an earlier one.

function findFirstOccurrence(sorted: number[], target: number): number {
  let left = 0;
  let right = sorted.length - 1;
  let result = -1;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (sorted[mid] === target) {
      result = mid;      // record this match...
      right = mid - 1;   // ...but keep searching left for an earlier one
    } else if (sorted[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
 
  return result;
}
 
findFirstOccurrence([1, 2, 2, 2, 3, 4], 2); // 1 (the first index where 2 appears)

The last occurrence is the mirror image — record the match, then search right instead of left. Both variants stay O(log n); the only change is what you do on a match, not the halving logic itself.

Searching a Rotated Sorted Array

A sorted array that's been rotated (e.g. [4, 5, 6, 7, 0, 1, 2] — sorted, then rotated at index 4) isn't fully sorted anymore, but it has a useful property: at least one half of any split is still sorted, and you can tell which half by comparing the endpoints.

function searchRotated(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] === target) return mid;
 
    if (nums[left] <= nums[mid]) {
      // Left half [left..mid] is sorted
      if (nums[left] <= target && target < nums[mid]) right = mid - 1;
      else left = mid + 1;
    } else {
      // Right half [mid..right] is sorted instead
      if (nums[mid] < target && target <= nums[right]) left = mid + 1;
      else right = mid - 1;
    }
  }
 
  return -1;
}
 
searchRotated([4, 5, 6, 7, 0, 1, 2], 0); // 4

Sign in to keep reading

The rest of this module is free — sign in with Google to unlock it and track your progress.

Sign in & Register
PreviousModule F-10: Intervals and Line SweepNext Module F-12: Capstone: DSA in Production — The Node.js Event Loop, Call Stack, and Queues

Discussion

0

Join the discussion

Loading comments...