Binary Search Coding Problems: 95 Questions with Solutions

How binary search works, step by step

1. 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.
2. 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.
3. hi moves to mid − 1 = 3, so 5 numbers leave the search in one step; 4 numbers remain between lo and hi.
4. 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.
5. lo moves to mid + 1 = 2, discarding 2 numbers at once; 2 numbers remain between lo and hi.
6. 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 95 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 81 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.

• Valid Perfect Square Easy
• Two Sum II - Input Array Is Sorted Medium

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

• Max Consecutive Ones III Medium
• Find First and Last Position of Element in Sorted Array Medium

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

• Search in Rotated Sorted Array Medium
• Find Minimum in Rotated Sorted Array Medium

Day 5

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

• Koko Eating Bananas Medium
• Capacity To Ship Packages Within D Days Medium

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.

• Preimage Size of Factorial Zeroes Function Hard

Next topic: Stack

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) / 2 overflowing when lo + hi passes 2³¹ − 1 in Java or C++; write lo + (hi - lo) / 2.
• An endless loop: lo = mid with a mid rounded down never shrinks a two-element range, so that variant needs mid = (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 (16)

• 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 (58)

• 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 (21)

• 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 77 problems on binary search
• Google 71 problems on binary search
• Microsoft 15 problems on binary search
• Meta 13 problems on binary search
• Adobe 6 problems on binary search
• Flipkart 6 problems on binary search
• Apple 4 problems on binary search
• Infosys 4 problems on binary search
• TCS 3 problems on binary search
• Uber 3 problems on binary search
• Atlassian 2 problems on binary search
• Bloomberg 2 problems on binary search

Other topics

• Arrays 667 problems
• Strings 282 problems
• Math 213 problems
• Hash Table 202 problems
• Dynamic Programming 195 problems
• Greedy 163 problems
• Sorting 156 problems
• Two Pointers 113 problems
• Matrix 107 problems
• Simulation 88 problems
• Bit Manipulation 83 problems
• Sliding Window 71 problems