HomeBinary Search
Binary Search
Halve the search space — on 1D arrays, on the answer, and in 2D grids.
51 shown
- BS on 1D Arrays
- Search X in Sorted ArrayDiscard half the array each comparisonanimatedEasy
- Lower BoundFirst index with a[i] ≥ xanimatedEasy
- Upper BoundFirst index with a[i] > xanimatedEasy
- Search Insert PositionLower bound: first index ≥ targetanimatedEasy
- Floor and Ceil in Sorted ArrayLargest ≤ x and smallest ≥ xanimatedEasy
- First and Last OccurrencelowerBound(x) and upperBound(x) − 1animatedEasy
- Count Occurrences in Sorted ArrayupperBound − lowerBoundanimatedEasy
- Search in Rotated Sorted Array IOne half is always sorted — use itanimatedMedium
- Search in Rotated Sorted Array IIDuplicates blur the sorted halfanimatedMedium
- Minimum in Rotated Sorted ArrayTake the min of the sorted halfanimatedMedium
- Rotation CountIndex of the minimum = rotationsanimatedEasy
- Single Element in Sorted ArrayParity of indices points the wayanimatedMedium
- Find Peak ElementClimb toward the higher neighbouranimatedMedium
- BS on Answers
- Square Root of a NumberLargest m with m·m ≤ xanimatedEasy
- Nth Root of a NumberLargest m with mⁿ ≤ xanimatedMedium
- Koko Eating BananasBinary search on the answer (eating speed)animatedMedium
- Minimum Days to Make M BouquetsSearch the bloom dayanimatedMedium
- Smallest Divisor Given a ThresholdBigger divisor → smaller sumanimatedMedium
- Capacity to Ship Packages in D DaysBigger capacity → fewer daysanimatedMedium
- Kth Missing Positive NumberMissing before a[i] = a[i] − (i+1)animatedEasy
- Aggressive CowsMaximize the minimum spacinganimatedHard
- Book AllocationMinimize the maximum pagesanimatedHard
- Split Array — Largest SumSame as book allocationanimatedHard
- Painter's PartitionMinimize the slowest painteranimatedMedium
- Minimize Max Distance to Gas StationBinary search on a real numberanimatedHard
- Median of Two Sorted ArraysBinary search the partitionanimatedHard
- Kth Element of Two Sorted ArraysPartition so the left holds kanimatedMedium
- BS on 2D Arrays
- Row with Maximum 1'sCount 1s per row with lower boundanimatedEasy
- Search in a 2D MatrixFlatten to one sorted arrayanimatedMedium
- Search in a 2D Matrix IIStaircase from the top-rightanimatedMedium
- Find Peak Element IIBinary search across columnsanimatedMedium
- Matrix MedianBinary search the value, count ≤ midanimatedHard
- Practice problems
- Count Occurrences in a Sorted ArrayLast occurrence minus first, plus oneanimatedEasy
- Find minimum in Rotated Sorted ArrayCompare mid with the right endanimatedEasy
- Find out how many times the array is rotatedThe index of the minimum is the rotation countanimatedEasy
- Single element in a Sorted ArrayPair parity tells you which side to keepanimatedMedium
- Find square root of a numberBinary search the answer, not the arrayanimatedMedium
- Find Nth root of a numberSame boundary search, with a poweranimatedMedium
- Find the smallest divisorBinary search the divisoranimatedMedium
- Capacity to Ship Packages Within D DaysBinary search the ship's capacityanimatedMedium
- Book Allocation ProblemMinimise the largest allocationanimatedHard
- Median of 2 sorted arraysBinary search the split pointanimatedHard
- Kth element of 2 sorted arraysThe median search, generalisedanimatedMedium
- Find row with maximum 1'sBinary search each row for its first 1animatedEasy
- Search in 2D matrix - IIStart at a corner where one move goes each wayanimatedHard
- Binary SearchHalve the range every stepanimatedMedium
- Apple Harvest (Koko Eating Bananas)Binary search the eating speedanimatedMedium
- Search in Rotated Sorted ArrayOne half is always sorted — check whichanimatedMedium
- Search a 2Treat the matrix as one flat sorted arrayanimatedMedium
- Kth Smallest in a Sorted MatrixBinary search the value, count what is belowanimatedMedium
- Minimum Shipping CapacityThe same capacity searchanimatedMedium