Binary search - cocoder39/coco39_LC GitHub Wiki

binary

• 278. First Bad Version
• 374. Guess Number Higher or Lower
• 69. Sqrt(x)
• 34. Search for a Range
• 162. Find Peak Element (input is not sorted, but search space can be reduced by half)
• 35. Search Insert Position
• 287. Find the Duplicate Number
• 275. H Index II
• 302. Smallest Rectangle Enclosing Black Pixels
• 1712. Ways to Split Array Into Three Subarrays

double

• 50. Pow(x, n)
• 29. Divide Two Integers

matrix

• 74. Search a 2D Matrix
• 240. Search a 2D Matrix II
• 1428. Leftmost Column with at Least a One
• 378. Kth Smallest Element in a Sorted Matrix (heap or binarySearch+LC.240)

rotate sorted array

• 153. Find Minimum in Rotated Sorted Array
• 154. Find Minimum in Rotated Sorted Array II
• 33. Search in Rotated Sorted Array
• 81. Search in Rotated Sorted Array II

range sum DP

• 363. Max Sum of Rectangle No Larger Than K
• 209. Minimum Size Subarray Sum (two pointers / binary search) vs 325. Maximum Size Subarray Sum Equals k (consider negative or not)
• 410. Split Array Largest Sum

longest increasing sequence DP

• 300. Longest Increasing Subsequence (dp / binary search)
• 334. Increasing Triplet Subsequence
• 354. Russian Doll Envelopes

find Kth

• 4. Median of Two Sorted Arrays
• 295. Find Median from Data Stream
• 1060. Missing Element in Sorted Array
• 1539. Kth Missing Positive Number

Enumerate potential results with using binary search to reduce search space

• 1760. Minimum Limit of Balls in a Bag
• 1802. Maximum Value at a Given Index in a Bounded Array
• 1838. Frequency of the Most Frequent Element
• 1891. Cutting Ribbons