Binary search observations

The idea: keep a range [low, high] where the answer can still be, and chop it in half each step. The only thing that bites you is knowing what low and high mean. If you can say that out loud, you're fine.

The easy way to never get confused: learn ONE template (find first true), use it for almost everything. That’s the whole post.

1. Classic: find an exact number in a sorted array

index:  0  1  2  3  4  5
value:  2  4  7  9 12 20    target 9 -> return 3

int low = 0, high = n - 1;
while (low <= high) {
    int mid = low + (high - low) / 2;
    if (nums[mid] == target) return mid;
    if (nums[mid] < target) low = mid + 1;   // too small, drop mid
    else high = mid - 1;                      // too big, drop mid
}
return -1;

We checked mid and it wasn't the target, so we throw it away (mid + 1 / mid - 1). Use low <= high because when they're equal there's still one box left to check.

2. The real pattern: find the FIRST true

Most problems aren’t “find x”. They look like this:

F F F T T T

False for a while, then flips to true and stays true. You want the first T. This is the template to memorize:

int low = 0, high = n;          // high = n if the answer can be "past the end"
while (low < high) {            // < , not <=
    int mid = low + (high - low) / 2;
    if (ok(mid)) high = mid;    // mid might be the answer, KEEP it
    else low = mid + 1;         // mid is false, DROP it
}
return low;

The only rule you need:

Can mid still be the answer? Yes -> high = mid. No -> low = mid + 1.

Quick example, first index with value >= 9:

value:  2  4  7  9 12 20
>= 9 ?  F  F  F  T  T  T     -> returns 3

Use low < high here (not <=). When they meet, that spot is the answer, nothing left to check.

3. Easy way for “find the MAX valid” (no second template)

If a problem says “largest X that works”, the pattern is T T T F F F. Just search for the first FALSE with the same template, then subtract one.

X:        1  2  3  4  5  6
works?    T  T  T  F  F  F
first false = index 3  ->  answer = 3 - 1 = 2 (last true)

// ok(x) = does x work?  we search for first x that FAILS
while (low < high) {
    int mid = low + (high - low) / 2;
    if (!ok(mid)) high = mid;   // first failing one
    else low = mid + 1;
}
return low - 1;                  // last working one

One template for both directions.

4. Lower bound and upper bound

Both are just “first true” with a different condition.

value:  1  3  3  3  5  7
index:  0  1  2  3  4  5

lowerBound(3): if (nums[mid] >= target) high = mid; else low = mid + 1;  // -> 1
upperBound(3): if (nums[mid] >  target) high = mid; else low = mid + 1;  // -> 4

Only >= vs >. Remember it as: lower bound = first one good enough (>=), upper bound = first one too big (>).

Get Anil Kumar’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Why useful:

• where to insert keeping sorted = lowerBound(x)
• count of x = upperBound(x) - lowerBound(x)

5. Start and end of a repeated number

This looks like a double flip and confuses people:

value:  1  2  5  5  5  5  8  9
== 5 ?  F  F  T  T  T  T  F  F

You can’t search “== 5” directly (two flips, no single half to drop). So run the two searches you already have:

int start = lowerBound(nums, 5);       // first >= 5  -> 2
int end   = upperBound(nums, 5) - 1;   // first > 5, minus 1 -> 5
// not present if start == n or nums[start] != 5

Rule: a double flip is never one search. Use lower bound + upper bound.

6. The confusions, flat list

• < vs <=: exact search uses <= (with mid - 1 / mid + 1). First-true uses < (with high = mid). Mixing <= with high = mid loops forever.
• mid vs mid + 1: just ask "can mid be the answer?". Keep -> high = mid. Drop -> mid + 1.
• what to return: first-true returns low. Max-valid returns low - 1. Exact returns mid or -1.
• overflow: always low + (high - low) / 2, never (low + high) / 2.
• initial high: exact search n - 1; insert position / "could be past end" n; search-the-answer max possible value.

7. How to pick (10 second check)

1. Exact value in a sorted array -> section 1.
2. “minimum X that works” / “first that satisfies” -> first true (section 2).
3. “maximum X that works” -> first false, return low - 1 (section 3).
4. “how many / where to insert / range of a number” -> lower & upper bound (sections 4, 5).

Most “minimize the max” / “maximize the min” problems are 2 or 3. The binary search never changes, only the ok() function does.

8. When it breaks

• Loops forever -> you used <= with high = mid. Use <.
• Off by one -> wrong >= vs >, or forgot the - 1 in max-valid. Trace [1, 2] by hand, the bug shows up instantly.
• Wrong on edges -> test target smaller than all, bigger than all, and size 1.

Cheat sheet

EXACT (sorted array):
  low=0, high=n-1; while(low<=high)
  hit -> return mid; small -> low=mid+1; big -> high=mid-1; else return -1

FIRST TRUE (F F F T T T):   the main one
  low=0, high=n; while(low<high)
  ok -> high=mid; else low=mid+1; return low


MAX VALID (T T T F F F):    same template, flipped
  search first FALSE the same way, return low-1

lowerBound(x): first i with a[i] >= x
upperBound(x): first i with a[i] >  x
count(x) = upperBound - lowerBound

range of x: start = lowerBound(x), end = upperBound(x) - 1
rule:   can mid be the answer?  yes -> high=mid.  no -> low=mid+1.
always: mid = low + (high-low)/2

Problems worth trying :-

Binary Search

Search a 2D Matrix

Koko Eating Bananas

Find Minimum In Rotated Sorted Array

Search In Rotated Sorted Array