Binary search [mp]

Micro pattern¶

Description¶

Repeatedly discard half of a search space while preserving an invariant that contains the answer.

Problems¶

Boundary search¶

Continue narrowing after finding a candidate to locate the first or last valid position.

• 278. First Bad Version (Top Easy)
• 35. Search Insert Position (Google Prep)
• 69. Sqrt(x) (Top Medium)

Structural search¶

Use a sorted half, slope, or partition violation to select the remaining half.

• 33. Search in Rotated Sorted Array (Top Medium)
• 162. Find Peak Element (Top Medium)
• 4. Median of Two Sorted Arrays (Top Hard)

Search over maintained tails¶

Binary-search a compact summary to find the state to extend or replace.

• 300. Longest Increasing Subsequence (Top Medium)
• 354. Russian Doll Envelopes (Dynamic Programming)
• 1964. Find the Longest Valid Obstacle Course at Each Position (Dynamic Programming)

Binary search on the answer¶

Search a numeric domain with a monotone counting or feasibility predicate.

• 69. Sqrt(x) (Top Medium)
• 378. Kth Smallest Element in a Sorted Matrix (Top Hard)