Binary Search Coding Problems: 189 Questions with Solutions
189 binary search coding problems — 24 easy · 115 medium · 50 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.
- Problems: 189
- By difficulty: 24 easy · 115 medium · 50 hard
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
- Cost: Free on every plan; sign in to run and submit
Binary search halves a sorted range every step, finding a value — or the boundary where a condition flips — in logarithmic time. Beyond searching a sorted array it answers "what is the smallest x for which this is possible?" over any monotone predicate. The problems here practise the search over indices, the search over answers, and the off-by-one care the boundaries demand.
New to binary search? Read the Binary Search tutorial first.
How binary search works, step by step
nums = [2, 5, 8, 12, 16, 23, 38, 56, 72], target = 8- The array is sorted, so if 8 is anywhere it lies between lo and hi, which start at the two ends. Each step looks at the middle and throws away the half that cannot hold it.
- mid = (0 + 8) / 2 = 4 and nums[4] = 16 is more than 8. Everything from index 4 on is at least 16, so the target can only be to the left.
- hi moves to mid − 1 = 3, so 5 numbers leave the search in one step; 4 numbers remain between lo and hi.
- mid = (0 + 3) / 2 = 1, rounded down, and nums[1] = 5 is less than 8. Everything up to index 1 is at most 5, so the target can only be to the right.
- lo moves to mid + 1 = 2, discarding 2 numbers at once; 2 numbers remain between lo and hi.
- mid = (2 + 3) / 2 = 2, rounded down, and nums[2] = 8: found at index 2 after 3 comparisons. Halving the range each time needs at most 4 looks for 9 numbers: O(log n), where a scan could need 9.
Binary Search study plan
14 of the 189 Binary Search problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 175 in the full list below are practice at your own pace. Then move on to Stack.
Day 1
Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.
- Binary Search Easy
- Search Insert Position Easy
- Sqrt(x) Easy
Day 2
Medium problems: the same pattern with one twist each. Name the twist before you code.
Day 3
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
Day 4
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
Day 5
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
Day 6
Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.
- Swim in Rising Water Hard
Day 7
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
- Nth Magical Number Hard
Day 8
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Binary Search: the essentials
When to reach for it
Sorted input, or sorted with a twist (rotated, rising then falling); the first or last position of something; and the less obvious case — "the minimum capacity, speed or time such that …", where any guess above the answer also works. Large bounds (answers up to 10⁹) together with a cheap feasibility check are the giveaway.
The pattern
Search for a boundary, not a value: the first x where ok(x) is true, given that ok is false up to some point and true from then on. Keep the invariant that the answer lies in [lo, hi], and discard the half that cannot hold it. The template below assumes ok(hi) is true; start hi at a value known to work.
def first_true(lo, hi, ok): # smallest x in [lo, hi] with ok(x)
while lo < hi:
mid = (lo + hi) // 2
if ok(mid):
hi = mid # mid may be the answer
else:
lo = mid + 1 # mid is not
return lo
Cost
O(log n) iterations. Searching an answer range of size R with an O(n) feasibility check costs O(n log R) — about 30 checks for R = 10⁹.
Common mistakes
mid = (lo + hi) / 2overflowing whenlo + hipasses 2³¹ − 1 in Java or C++; writelo + (hi - lo) / 2.- An endless loop:
lo = midwith a mid rounded down never shrinks a two-element range, so that variant needsmid = (lo + hi + 1) / 2. - Mixing closed
[lo, hi]and half-open[lo, hi)conventions inside one loop. - Binary searching a predicate that is not monotone, where halving throws the answer away.
Start with
- Binary Search: the plain sorted-array search.
- Search in Rotated Sorted Array: deciding which half is sorted.
- Koko Eating Bananas: searching over the answer.
All binary search problems
Easy (24)
- Count BST Nodes That Lie in a Given Range Tree, Depth-First Search
- Ceil in BST Tree
- Count Complete Tree Nodes Bit Manipulation, Tree
- Range Sum of BST Tree, Depth-First Search
- Search in a Binary Search Tree Tree
- Find Nth Root of M Math
- Find Target Indices After Sorting Array Array, Sorting
- Element Appearing More Than 25% In Sorted Array Array
- Sqrt(x) Math
- Kth Missing Positive Number Array
- Find Smallest Letter Greater Than Target Array
- Find the Distance Value Between Two Arrays Array, Two Pointers
- Find Transition Point Array
- The K Weakest Rows in a Matrix Array, Sorting, Heap
- Count Negative Numbers in a Sorted Matrix Array, Matrix
- Maximum Count of Positive Integer and Negative Integer Array, Counting
- Minimum Common Value Array, Hash Table, Two Pointers
- Count Pairs Whose Sum is Less than Target Array, Two Pointers, Sorting
- Special Array With X Elements Greater Than or Equal X Array, Sorting, Counting Sort
- Arranging Coins Math
- Valid Perfect Square Math
- Sqrt(x) Math
- Search Insert Position Array
- Binary Search Array
Medium (115)
- Implement Router Array, Hash Table, Queue
- Longest Uploaded Prefix Hash Table, Union Find, Design
- Range Frequency Queries Array, Hash Table, Segment Tree
- Tweet Counts Per Frequency Hash Table, Sorting, Ordered Set
- Snapshot Array Array, Hash Table, Design
- Time Based Key-Value Store Hash Table, String, Design
- Online Election Array, Hash Table, Design
- My Calendar II Array, Ordered Set, Prefix Sum
- My Calendar I Array, Ordered Set, Segment Tree
- Predecessor and Successor in BST Tree
- Inorder Successor in BST Tree, Depth-First Search
- Floor in BST Tree
- Closest Nodes Queries in a Binary Search Tree Tree, Depth-First Search, Array
- Construct Binary Search Tree from Preorder Traversal Array, Stack, Tree
- Maximum Binary Tree II Tree
- Insert into a Binary Search Tree Tree
- Convert BST to Greater Tree Tree, Depth-First Search
- Delete Node in a BST Tree, Recursion
- Lowest Common Ancestor of a Binary Search Tree Tree, Depth-First Search
- Adjacent Increasing Subarrays Detection II Array
- Closest Equal Element Queries Array, Hash Table
- Find Longest Special Substring That Occurs Thrice I Hash Table, String, Sliding Window
- Minimize Maximum Component Cost Union Find, Graph, Sorting
- Minimum Time for K Connected Components Union Find, Graph, Sorting
- Maximum Total Damage With Spell Casting Array, Hash Table, Two Pointers
- Count Nodes With the Highest Score Array, Tree, Depth-First Search
- Maximize the Profit as the Salesman Array, Dynamic Programming, Sorting
- Two Best Non-Overlapping Events Array, Dynamic Programming, Sorting
- Range Sum of Sorted Subarray Sums Array, Two Pointers, Sorting
- K-th Element of Two Sorted Arrays Array, Divide and Conquer
- Minimum Absolute Difference Between Elements With Constraint Array, Ordered Set, Binary Indexed Tree
- Minimum Sum of Squared Difference Array, Greedy, Sorting
- Earliest Second to Mark Indices I Array, Greedy
- Median in a Row-Wise Sorted Matrix Array, Matrix
- Minimum Number of Seconds to Make Mountain Height Zero Array, Math, Heap (Priority Queue)
- Maximum Number of Alloys Array
- Minimum Operations to Make All Array Elements Equal Array, Sorting, Prefix Sum
- Minimum Absolute Sum Difference Array, Sorting, Ordered Set
- Count Number of Rectangles Containing Each Point Array, Hash Table, Sorting
- Maximum Tastiness of Candy Basket Array, Greedy, Sorting
- Minimized Maximum of Products Distributed to Any Store Array, Greedy
- Minimum Absolute Difference Queries Array, Hash Table, Prefix Sum
- Maximum Side Length of a Square with Sum Less than or Equal to Threshold Array, Matrix, Prefix Sum
- Sum of Mutated Array Closest to Target Array, Sorting
- Heaters Array, Sorting, Two Pointers
- Maximize Win From Two Segments Array, Sliding Window
- Count the Number of Fair Pairs Array, Two Pointers, Sorting
- Shortest Subarray to be Removed to Make Array Sorted Array, Two Pointers, Monotonic Stack
- Ways to Split Array Into Three Subarrays Array, Two Pointers, Prefix Sum
- Smallest Subarrays With Maximum Bitwise OR Array, Bit Manipulation, Sliding Window
- Minimize the Maximum of Two Arrays Math, Number Theory
- Ugly Number III Math, Number Theory, Combinatorics
- Plates Between Candles Array, String, Prefix Sum
- Compare Strings by Frequency of the Smallest Character Array, Hash Table, String
- Longest Square Streak in an Array Array, Hash Table, Dynamic Programming
- Minimize Maximum of Array Array, Greedy, Prefix Sum
- Maximum Number of Groups Entering a Competition Array, Math, Greedy
- Longest Subsequence With Limited Sum Array, Greedy, Sorting
- K-th Smallest Prime Fraction Array, Sorting, Heap (Priority Queue)
- Most Beautiful Item for Each Query Array, Sorting
- Find the Safest Path in a Grid Array, Matrix, Breadth-First Search
- Longest Arithmetic Subsequence Array, Hash Table, Dynamic Programming
- Maximum Number of Removable Characters Array, String, Two Pointers
- Divide Chocolate Array, Greedy
- Successful Pairs of Spells and Potions Array, Sorting, Two Pointers
- Search a 2D Matrix II Array, Matrix, Divide and Conquer
- Find Right Interval Array, Sorting
- House Robber IV Array, Greedy
- Minimize the Maximum Difference of Pairs Array, Greedy, Sorting
- Maximum Candies Allocated to K Children Array
- Peak Index in a Mountain Array Array
- H-Index II Array
- Find the Smallest Divisor Given a Threshold Array
- Maximum Value at a Given Index in a Bounded Array Greedy, Math
- Find the Student That Will Replace the Chalk Array, Prefix Sum, Simulation
- Minimum Limit of Balls in a Bag Array
- Magnetic Force Between Two Balls Array, Sorting, Greedy
- Minimum Number of Days to Make m Bouquets Array
- Capacity to Ship Packages Within D Days Array
- Find First and Last Position of Element in Sorted Array Array
- Find Minimum in Rotated Sorted Array II Array
- Search in Rotated Sorted Array II Array
- Maximum Beauty of an Array After Applying Operation Array, Sliding Window, Sorting
- Swap For Longest Repeated Character Substring String, Sliding Window, Hash Table
- Get Equal Substrings Within Budget String, Sliding Window, Prefix Sum
- Maximize the Confusion of an Exam String, Sliding Window, Prefix Sum
- Frequency of the Most Frequent Element Array, Sliding Window, Greedy
- Number of Subsequences That Satisfy the Given Sum Condition Array, Two Pointers, Sorting
- Maximum Distance Between a Pair of Values Array, Two Pointers
- Sum of Square Numbers Math, Two Pointers
- Minimum Time to Repair Cars Array, Greedy
- Maximum Number of Integers to Choose From a Range I Hash Table, Greedy
- Number of Matching Subsequences String, Two Pointers
- Reach a Number Math
- Path With Minimum Effort Array, Depth-First Search, Breadth-First Search
- Nth Digit Math
- 132 Pattern Array, Stack, Monotonic Stack
- Find K Closest Elements Array, Two Pointers, Sorting
- Kth Smallest Element in a Sorted Matrix Array, Sorting, Heap
- Valid Triangle Number Array, Two Pointers, Greedy
- Maximum Length of Repeated Subarray Array, Dynamic Programming, Sliding Window
- Minimum Operations to Reduce X to Zero Array, Hash Table, Sliding Window
- Subarray Product Less Than K Array, Sliding Window, Prefix Sum
- Search a 2D Matrix Array, Matrix
- Longest Increasing Subsequence Array, Dynamic Programming
- Single Element in a Sorted Array Array
- Capacity To Ship Packages Within D Days Array, Greedy
- Koko Eating Bananas Array
- Find First and Last Position of Element in Sorted Array Array
- Find Peak Element Array
- Find Minimum in Rotated Sorted Array Array
- Search in Rotated Sorted Array Array
- Max Consecutive Ones III Array, Sliding Window
- Two Sum II - Input Array Is Sorted Array, Two Pointers
- Find the Duplicate Number Array, Two Pointers
Hard (50)
- Range Module Segment Tree, Ordered Set, Design
- Data Stream as Disjoint Intervals Design, Ordered Set
- Last Day Where You Can Still Cross Array, Depth-First Search, Breadth-First Search
- Minimum Sum of Values by Dividing Array Array, Dynamic Programming, Bit Manipulation
- Find Maximum Non-decreasing Array Length Array, Dynamic Programming, Stack
- Maximum Strictly Increasing Cells in a Matrix Array, Hash Table, Dynamic Programming
- Minimum Number of Removals to Make Mountain Array Array, Dynamic Programming, Greedy
- Max Sum of Rectangle No Larger Than K Array, Matrix, Ordered Set
- Minimum Operations to Make the Array K-Increasing Array, Dynamic Programming
- Maximum Profit in Job Scheduling Array, Dynamic Programming, Sorting
- Super Egg Drop Math, Dynamic Programming
- Partition Array Into Two Arrays to Minimize Sum Difference Array, Bit Manipulation, Bitmask
- My Calendar III Segment Tree, Prefix Sum, Ordered Set
- Minimum Interval to Include Each Query Array, Sorting, Heap (Priority Queue)
- Find the Number of Subarrays Where Boundary Elements Are Maximum Array, Stack, Monotonic Stack
- Maximum Sum Queries Array, Sorting, Monotonic Stack
- Minimum Operations to Make a Subsequence Array, Hash Table, Greedy
- Find Building Where Alice and Bob Can Meet Array, Monotonic Stack, Heap (Priority Queue)
- Minimum Cost to Make Array Equal Array, Greedy, Sorting
- Maximize the Minimum Powered City Array, Greedy, Prefix Sum
- Number of Flowers in Full Bloom Array, Sorting, Prefix Sum
- Kth Smallest Product of Two Sorted Arrays Array, Two Pointers
- Maximum Fruits Harvested After at Most K Steps Array, Sliding Window, Prefix Sum
- Count Subarrays With Score Less Than K Array, Sliding Window, Prefix Sum
- Number of Subarrays With AND Value of K Array, Bit Manipulation, Segment Tree
- Number of Excellent Pairs Array, Hash Table, Bit Manipulation
- Sum of Floored Pairs Array, Math, Prefix Sum
- Subsequence With the Minimum Score String, Two Pointers
- Sum of Scores of Built Strings String, String Matching, Rolling Hash
- Make Array Strictly Increasing Array, Dynamic Programming, Sorting
- Maximum Number of Events That Can Be Attended II Array, Dynamic Programming, Sorting
- Create Sorted Array Through Instructions Array, Divide and Conquer, Binary Indexed Tree
- Reverse Pairs Array, Divide and Conquer, Binary Indexed Tree
- Minimum Number of Operations to Make Array Continuous Array, Hash Table, Sliding Window
- Escape the Spreading Fire Array, Matrix, Breadth-First Search
- Maximum Number of Groups With Increasing Length Array, Greedy, Sorting
- Maximum Number of Tasks You Can Assign Array, Greedy, Sorting
- Find the Kth Smallest Sum of a Matrix With Sorted Rows Array, Matrix, Heap
- Russian Doll Envelopes Array, Dynamic Programming, Sorting
- Maximum Running Time of N Computers Array, Greedy, Sorting
- Minimum Time to Complete Trips Array
- Kth Smallest Number in Multiplication Table Math
- Split Array Largest Sum Array, Greedy, Dynamic Programming
- Shortest Subarray with Sum at Least K Array, Prefix Sum, Sliding Window
- Find K-th Smallest Pair Distance Array, Two Pointers, Sorting
- Find Subarray With Bitwise OR Closest to K Bit Manipulation, Array, Segment Tree
- Smallest Good Base Math, Number Theory
- Preimage Size of Factorial Zeroes Function Math, Number Theory
- Nth Magical Number Math, Number Theory
- Swim in Rising Water Array, Depth-First Search, Breadth-First Search
Companies that ask binary search problems
- Amazon 163 problems on binary search
- Google 148 problems on binary search
- Microsoft 33 problems on binary search
- Meta 22 problems on binary search
- Flipkart 9 problems on binary search
- Adobe 6 problems on binary search
- Uber 6 problems on binary search
- Apple 5 problems on binary search
- Arcesium 5 problems on binary search
- Intuit 5 problems on binary search
- PhonePe 5 problems on binary search
- Razorpay 5 problems on binary search
Next topic: Stack