Skip to main content
Binary Search

Find Boundary

Find the first index where a condition becomes true (or the last where it's false). Use binary search with a predicate function. This generalizes lower_bound and upper_bound.

O(log n)
·
O(1)

How It Works

Boundary binary search finds the exact index where a predicate transitions — the first element where a condition becomes true, or the last where it stays false. Picture the array as a run of falses followed by a run of trues; the algorithm keeps low in the false region and high in the true region, halving the gap until they meet at the boundary.

This generalizes lower_bound (first element >= target) and upper_bound (first element > target), and together those bracket every occurrence of a value, so counting duplicates or finding first-and-last positions takes two O(log n) searches. The habit of framing problems as 'find the transition point of a predicate' is also the mental bridge to binary searching on answers.

Step-by-Step Visualization

Find first True in [F,F,F,T,T,T]
L
F
0
F
1
mid
F
2
T
3
T
4
R
T
5
arr[mid]F → left = mid+1
1/4

Code

Java
static int firstTrue(boolean[] arr) {
  int left = 0, right = arr.length - 1;

  while (left < right) {
    int mid = left + (right - left) / 2;
    if (arr[mid]) {
      right = mid;     // mid could be the answer
    } else {
      left = mid + 1;  // mid is definitely not
    }
  }

  return left; // First true position
}

// Example: firstTrue(new boolean[]{false,false,false,true,true,true}) → 3

Tips & Gotchas

1Use left < right (not <=) with this template
2When condition is true, set right = mid (keep mid as candidate)
3When condition is false, set left = mid + 1 (discard mid)
4After loop, left = right = answer

Practice Problems

  • 1Find First and Last Position of Element in Sorted Array
  • 2First Bad Version
  • 3Peak Index in a Mountain Array
  • 4Find Smallest Letter Greater Than Target

About the Binary Search Pattern

If the search space is sorted (or has a monotonic property), you can eliminate half of it with each comparison. This reduces O(n) linear search to O(log n). Works on arrays, answer spaces, and even abstract conditions.

Key insight

When you see 'subarray', 'contiguous', or 'in-place', think arrays. The key is reducing brute-force O(n²) to O(n) using sliding window, two pointers, or prefix sums.

Common Array Interview Problems

  • Two Sum
  • Best Time to Buy & Sell Stock
  • Maximum Subarray
  • Merge Intervals
  • Product of Array Except Self
  • Container With Most Water

Frequently Asked Questions

What is the difference between lower_bound and upper_bound?

lower_bound returns the first index whose element is greater than or equal to the target, while upper_bound returns the first index strictly greater. Their difference is the count of occurrences, and lower_bound is also the correct insertion point that keeps equal elements' order.

How do I avoid the infinite loop when searching for a boundary?

When the loop keeps low and high adjacent-converging (while low < high), pair mid = low + (high − low) / 2 with updates high = mid and low = mid + 1. If you instead need the last-true element with low = mid, bias mid upward with (high − low + 1) / 2, or the two-element case never shrinks.