Binary Search Beyond the Basics: 5 Advanced Variations

Binary search is not just "find x in a sorted array." In interviews, you will see variations: find the first occurrence, the last occurrence, search in a rotated array, or even binary search on the answer when the problem has a monotonic predicate. This guide covers five essential variants with templates you can adapt.

1. Standard Binary Search

Find the index of target in a sorted array, or -1 if not found. Use inclusive bounds and loop while left ≤ right. The key is: when arr[mid] < target, search right (left = mid + 1); when arr[mid] > target, search left (right = mid - 1).

function binarySearch(arr: number[], target: number): number {
  let left = 0, right = arr.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

2. First Occurrence (Lower Bound)

Find the index of the first element ≥ target (or first occurrence of target). When arr[mid] ≥ target, the answer could be mid or to the left, so set right = mid. Use right = mid (not mid - 1) and avoid returning early — keep narrowing until left === right.

function firstOccurrence(arr: number[], target: number): number {
  let left = 0, right = arr.length;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] < target) left = mid + 1;
    else right = mid;
  }
  return left < arr.length && arr[left] === target ? left : -1;
}

// Or: find first index where arr[i] >= target (lower_bound)
function lowerBound(arr: number[], target: number): number {
  let left = 0, right = arr.length;
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] < target) left = mid + 1;
    else right = mid;
  }
  return left;
}

3. Last Occurrence (Upper Bound)

Find the index of the last element ≤ target (or last occurrence of target). When arr[mid] ≤ target, the answer could be mid or to the right, so set left = mid + 1. Return right (or left - 1) as the last valid index.

function lastOccurrence(arr: number[], target: number): number {
  let left = 0, right = arr.length - 1;
  let result = -1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] === target) {
      result = mid;
      left = mid + 1;
    } else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return result;
}

// Upper bound: first index where arr[i] > target
function upperBound(arr: number[], target: number): number {
  let left = 0, right = arr.length;
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] <= target) left = mid + 1;
    else right = mid;
  }
  return left;
}

4. Rotated Sorted Array

The array is sorted but rotated (e.g., [4,5,6,7,0,1,2]). One half of arr[left..right] is always sorted. Compare arr[mid] with arr[left] (or arr[right]) to determine which half is sorted, then check if target is in that half.

function searchRotated(arr: number[], target: number): number {
  let left = 0, right = arr.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] === target) return mid;

    if (arr[left] <= arr[mid]) {
      if (arr[left] <= target && target < arr[mid]) right = mid - 1;
      else left = mid + 1;
    } else {
      if (arr[mid] < target && target <= arr[right]) left = mid + 1;
      else right = mid - 1;
    }
  }
  return -1;
}

// Find minimum in rotated array
function findMinRotated(arr: number[]): number {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] > arr[right]) left = mid + 1;
    else right = mid;
  }
  return arr[left];
}

5. Binary Search on Answer

The answer space is a range (e.g., 1 to max). There is a monotonic predicate: for some threshold x, all values ≤ x satisfy P, and all > x do not (or vice versa). Binary search on the answer to find the smallest (or largest) valid value.

Classic example: Koko Eating Bananas. Given piles and h hours, find the minimum eating speed. For speed k, can Koko finish in ≤ h hours? This is monotonic: if k works, k+1 works. Binary search on k.

function minEatingSpeed(piles: number[], h: number): number {
  let left = 1, right = Math.max(...piles);

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (canFinish(piles, mid, h)) right = mid;
    else left = mid + 1;
  }
  return left;
}

function canFinish(piles: number[], speed: number, h: number): boolean {
  let hours = 0;
  for (const p of piles) hours += Math.ceil(p / speed);
  return hours <= h;
}

When to Use Search on Answer

• Minimize the maximum / maximize the minimum: Split Array Largest Sum, Capacity to Ship Packages.
• Find smallest/largest valid value: Koko Eating Bananas, Minimum Number of Days to Make m Bouquets.
• Predicate is expensive but monotonic: Binary search reduces calls to the predicate from O(n) to O(log n).

Template Summary

Practice with our interactive Binary Search animation.

• Time Complexity Cheat Sheet
• Top 10 LeetCode Patterns Every FAANG Candidate Must Know