Standard binary search, boundary finding, rotated arrays, and search-space binary search -- templates with correct boundary handling

Binary Search

Binary search is simple in concept -- cut the search space in half each step -- but notoriously tricky to implement correctly. Off-by-one errors in boundary handling cause more bugs than any other part. This article gives you battle-tested templates.

Standard Binary Search

Find if a target exists in a sorted array.

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

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

  return -1;
}

Time: O(log n), Space: O(1).

Why left + Math.floor((right - left) / 2) instead of Math.floor((left + right) / 2)? The latter can overflow in languages with fixed-size integers. In JavaScript/TypeScript it does not matter, but it is a good habit and interviewers notice.

Left Boundary (First Occurrence)

Find the first position where nums[i] >= target. This is the foundation for many variations.

function leftBound(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length; // note: right = length, not length - 1

  while (left < right) {   // note: strict <, not <=
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid; // note: right = mid, not mid - 1
    }
  }

  return left; // left === right, this is the insertion point
}

Returns the index of the first element >= target.
If all elements are less than target, returns nums.length.
To check if target actually exists: left < nums.length && nums[left] === target.

Right Boundary (Last Occurrence)

Find the last position where nums[i] <= target.

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

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

  return left - 1; // the last element <= target
}

Finding First and Last Position

Combine left and right boundary to solve "find the range of a target in a sorted array":

function searchRange(nums: number[], target: number): [number, number] {
  const first = leftBound(nums, target);

  if (first >= nums.length || nums[first] !== target) {
    return [-1, -1];
  }

  const last = rightBound(nums, target);
  return [first, last];
}

Time: O(log n), Space: O(1). Two binary searches, each O(log n).

Search in Rotated Sorted Array

A sorted array rotated at some pivot: [4, 5, 6, 7, 0, 1, 2]. Find a target.

The key insight: at least one half of the array around mid is always sorted. Check which half is sorted, then decide if the target lies in that half.

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;

    // Left half is sorted
    if (nums[left] <= nums[mid]) {
      if (target >= nums[left] && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    // Right half is sorted
    else {
      if (target > nums[mid] && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }

  return -1;
}

Time: O(log n), Space: O(1).

Find Minimum in Rotated Sorted Array

function findMin(nums: number[]): number {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);

    if (nums[mid] > nums[right]) {
      // Minimum is in right half
      left = mid + 1;
    } else {
      // Minimum is in left half (including mid)
      right = mid;
    }
  }

  return nums[left];
}

Search Space Binary Search

This is the most powerful and most underused variant. Instead of searching in an array, you binary search over the answer space. This applies to "minimize the maximum" or "maximize the minimum" problems.

Template: Minimize the Maximum

function minimizeMax(/* problem params */): number {
  let left = /* minimum possible answer */;
  let right = /* maximum possible answer */;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);

    if (canAchieve(mid)) {
      right = mid;    // mid works, try smaller
    } else {
      left = mid + 1; // mid doesn't work, need larger
    }
  }

  return left;
}

function canAchieve(threshold: number): boolean {
  // Check if it's possible to satisfy the constraint
  // with this threshold. Usually a greedy O(n) check.
  return true;
}

Example: Koko Eating Bananas

Koko has piles of bananas. She can eat k bananas per hour. Find the minimum k such that she finishes all piles within h hours.

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

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);

    const hoursNeeded = piles.reduce(
      (sum, pile) => sum + Math.ceil(pile / mid),
      0
    );

    if (hoursNeeded <= h) {
      right = mid;    // can eat slower
    } else {
      left = mid + 1; // need to eat faster
    }
  }

  return left;
}

Time: O(n log m) where n = number of piles, m = max pile size. Space: O(1).

Example: Split Array Largest Sum

Split an array into k subarrays to minimize the largest subarray sum.

function splitArray(nums: number[], k: number): number {
  let left = Math.max(...nums);               // at least the max element
  let right = nums.reduce((a, b) => a + b, 0); // at most the total sum

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);

    if (canSplit(nums, k, mid)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }

  return left;
}

function canSplit(nums: number[], k: number, maxSum: number): boolean {
  let splits = 1;
  let currentSum = 0;

  for (const num of nums) {
    if (currentSum + num > maxSum) {
      splits++;
      currentSum = num;
      if (splits > k) return false;
    } else {
      currentSum += num;
    }
  }

  return true;
}

Boundary Handling Cheat Sheet

The two main styles and when to use each:

Style	Loop condition	Update	Returns
`left <= right`	Use for exact match	`left = mid + 1`, `right = mid - 1`	Index of target or -1
`left < right`	Use for boundary finding	`left = mid + 1`, `right = mid`	Convergence point

Common pitfall with left < right: when updating left, you must use mid + 1 (not mid), otherwise you get an infinite loop when left === mid (which happens when right - left === 1).

When to Use Binary Search

The input is sorted (or has a monotonic property)
You need to find a boundary (first/last element satisfying a condition)
You need to minimize/maximize something and can check feasibility
The search space is monotonic: if condition holds for x, it holds for all values on one side of x
The problem constraint says n up to 10^9 -- too large for linear scan, needs O(log n)

Complexity Summary

Problem	Time	Space
Standard binary search	O(log n)	O(1)
Left/right boundary	O(log n)	O(1)
Search in rotated array	O(log n)	O(1)
Koko eating bananas	O(n log m)	O(1)
Split array largest sum	O(n log S)	O(1)

Binary search on the answer space is a pattern worth internalizing. Whenever a problem asks "what is the minimum X such that Y is possible," think binary search.

Binary Search

On this page