Binary Search

Binary search repeatedly halves a sorted (or monotonic) search space, finding an answer in O(log n) instead of O(n). Beyond sorted arrays, reach for it whenever you can phrase the problem as 'find the smallest or largest value for which a condition flips from false to true.'

20 LeetCode problems solved with the Binary Search pattern. Practice them with spaced repetition so the pattern sticks.

• Binary SearchEASY · O(log n)
• Capacity To Ship Packages Within D DaysMEDIUM · O(n * log(sum))
• Find First and Last Position of Element in Sorted ArrayMEDIUM · O(log n)
• Find in Mountain ArrayHARD · O(log n)
• Find K Closest ElementsMEDIUM · O(log(n - k) + k)
• Find Minimum in Rotated Sorted ArrayMEDIUM · O(log n)
• Find Peak ElementMEDIUM · O(log n)
• First Bad VersionEASY · O(log n)
• Guess Number Higher or LowerEASY · O(log n)
• Koko Eating BananasMEDIUM · O(n log m)
• Lowest Common Ancestor of a Binary Search TreeMEDIUM · O(h)
• Median of Two Sorted ArraysHARD · O(log (m+n))
• Search a 2D MatrixMEDIUM · O(log(m*n))
• Search in a Binary Search TreeEASY · O(h)
• Search in Rotated Sorted ArrayMEDIUM · O(log n)
• Search in Rotated Sorted Array IIMEDIUM · O(log n)
• Search Insert PositionEASY · O(log n)
• Split Array Largest SumHARD · O(n * log(sum))
• Sqrt(x)EASY · O(log n)
• Successful Pairs of Spells and PotionsMEDIUM · O((n + m) log m)