1582 articles
Find the secret number between 1 and n using the guess() API in O(log n) calls. Master the exact binary search template used in all interactive/guessing problems and understand why the API return values map directly to the lo/hi update rules.
LC 1351 asks you to count negatives in a matrix sorted both row-wise and column-wise. The O(m+n) staircase approach is optimal; an O(m log n) binary-search-per-row alternative is also acceptable. Both demonstrate how sorted structure eliminates naive O(mn) scanning.
LC 367 asks if a positive integer is a perfect square without using built-in sqrt. Binary search on [1, num] for a value k where k*k == num. Also learn the elegant O(sqrt(n)) odd-number identity. A classic easy binary search problem at Google and Apple.
LC 744 finds the smallest letter in a circular sorted array that is strictly greater than the target. Left-boundary binary search with modular wrap-around handles the circular case elegantly. A clean variant that extends the standard left-boundary template.
LC 911 requires answering repeated queries "who is leading at time t?" in O(log n) per query. Precompute the leader at each vote event, then use right-boundary binary search on the times array to answer each query. Classic precompute-and-query design.