Skip to main content

Complete Binary Search Problems & Resources Guide

· 16 min read

Hey everyone! Binary Search is one of the most elegant and powerful techniques in DSA, yet it's often underestimated. I've spent considerable time mastering binary search for both tech interviews and competitive programming, and I wanted to share a complete guide that covers everything you need.

The key insight that changed everything for me: Binary Search isn't just about finding elements in sorted arrays. It's a problem-solving paradigm that applies whenever you can define a monotonic property (if something works for x, it works for all values greater/smaller than x). Once you understand this, you'll see binary search opportunities everywhere.

What makes Binary Search tricky? The basic algorithm is simple, but recognizing when to apply it and implementing it bug-free (especially edge cases) is challenging. The real power comes from "binary search on answer", a technique that turns many optimization problems into search problems.

For Tech Interviews: You need to master the classic binary search template, handle edge cases flawlessly, and recognize binary search on answer patterns. About 50-60 well-understood problems is sufficient. Most interview problems are medium difficulty.

For Competitive Programming: You need deep understanding of searching on answer spaces, optimization techniques, binary search on floating point, and combining binary search with other algorithms. This requires 100-150+ problems.

Best Learning Resources​

Video Resources for Interview Prep​

NeetCode - Binary Search Playlist - The absolute best for learning interview binary search patterns. Clear explanations with Python implementations. Covers classic search, search on answer, and all important variations.

take U forward (Striver) - Binary Search Series - Comprehensive coverage with detailed explanations. Extremely thorough with C++/Java code. Around 30+ hours of content covering basics to advanced.

Abdul Bari - Binary Search - Best for understanding the theory and analysis. Crystal clear explanation of how binary search achieves O(log n) complexity.

Back To Back SWE - Binary Search - Excellent breakdown of the thought process and common pitfalls. Great for understanding boundary conditions.

Video Resources for Competitive Programming​

Errichto - Binary Search Lectures - Phenomenal coverage of binary search for CP. Covers binary search on answer, floating point binary search, and advanced applications.

SecondThread - Binary Search Techniques - Advanced binary search applications in competitive programming. Shows how to combine binary search with other techniques.

William Fiset - Binary Search Algorithms - Clear visualizations and explanations of various binary search variants.

Written Resources​

For Interviews:

For Competitive Programming:

Books Worth Reading​

Cracking the Coding Interview - Good introduction to binary search with interview problems.

Competitive Programming 4 - Chapter on binary search with advanced applications and optimization techniques.

Introduction to Algorithms (CLRS) - Rigorous treatment of binary search with mathematical analysis.

Elements of Programming Interviews - Excellent binary search problems with detailed solutions.

Interview Problems (60 Total)​

Master the fundamental template. If you can't implement these bug-free, everything else will be difficult.

  1. Binary Search
  2. Search Insert Position
  3. First Bad Version
  4. Valid Perfect Square
  5. Arranging Coins
  6. Sqrt(x)
  7. Guess Number Higher or Lower
  8. Find Smallest Letter Greater Than Target
  9. Peak Index in a Mountain Array
  10. Count Negative Numbers in a Sorted Matrix

Phase 2: Finding Boundaries​

Learn to find first/last occurrence and handle duplicates. This is crucial for many applications.

  1. Find First and Last Position of Element in Sorted Array
  2. Find Peak Element
  3. Single Element in a Sorted Array
  4. Search in Rotated Sorted Array
  5. Search in Rotated Sorted Array II
  6. Find Minimum in Rotated Sorted Array
  7. Find Minimum in Rotated Sorted Array II
  8. Time Based Key-Value Store
  9. Random Pick with Weight
  10. Find K Closest Elements

Phase 3: Binary Search on Answer​

The most important pattern. Learning to search on the answer space rather than index space.

  1. Koko Eating Bananas
  2. Minimum Number of Days to Make m Bouquets
  3. Capacity To Ship Packages Within D Days
  4. Kth Smallest Element in a Sorted Matrix
  5. Find the Smallest Divisor Given a Threshold
  6. Magnetic Force Between Two Balls
  7. Minimize Max Distance to Gas Station
  8. Split Array Largest Sum
  9. Divide Chocolate
  10. Cutting Ribbons

Phase 4: 2D Binary Search & Matrix Problems​

Binary search in 2D spaces and matrix applications.

  1. Search a 2D Matrix
  2. Search a 2D Matrix II
  3. Find a Peak Element II
  4. Kth Smallest Number in Multiplication Table
  5. K-th Smallest Prime Fraction
  6. Find K-th Smallest Pair Distance
  7. Ugly Number III
  8. Kth Smallest Product of Two Sorted Arrays

Phase 5: Advanced Binary Search on Answer​

Complex applications requiring creative problem formulation.

  1. Median of Two Sorted Arrays
  2. Find Minimum in Rotated Sorted Array
  3. Shortest Subarray with Sum at Least K
  4. Maximum Number of Removable Characters
  5. Maximum Number of Tasks You Can Assign
  6. Minimize the Difference Between Target and Chosen Elements
  7. Maximum Running Time of N Computers
  8. Maximum Tastiness of Candy Basket
  9. Minimized Maximum of Products Distributed to Any Store
  10. Minimum Time to Complete Trips
  11. Maximum Number of Alloys
  12. Minimum Limit of Balls in a Bag

Phase 6: Binary Search with Other Techniques​

Combining binary search with greedy, DP, or other algorithms.

  1. Find Right Interval
  2. Maximum Length of Repeated Subarray
  3. Longest Duplicate Substring
  4. Longest Increasing Subsequence
  5. Russian Doll Envelopes
  6. Maximum Profit in Job Scheduling
  7. Count of Smaller Numbers After Self
  8. The K Weakest Rows in a Matrix
  9. Successful Pairs of Spells and Potions
  10. Maximum Candies Allocated to K Children

Competitive Programming Problems​

AtCoder Binary Search Problems​

  1. ABC 077 C - Snuke Festival
  2. ABC 143 D - Triangles
  3. ABC 155 D - Pairs
  4. ABC 172 D - Sum of Divisors
  5. ABC 192 D - Base n
  6. ABC 205 D - Kth Excluded
  7. ABC 231 D - Neighbors
  8. ABC 248 D - Range Count Query
  9. ABC 255 D - ±1 Operation 1
  10. ABC 268 D - Unique Username
  11. ABC 279 D - Freefall
  12. ABC 294 E - 2xN Grid
  13. ABC 302 D - Impartial Gift
  14. ABC 319 E - Bus Stops
  15. ARC 054 B - Moist

CSES Binary Search Problems​

  1. Factory Machines
  2. Array Division
  3. Sum of Four Values
  4. Nearest Smaller Values
  5. Subarray Distinct Values
  6. Maximum Subarray Sum II
  7. Movie Festival II
  8. Reading Books

Codeforces Binary Search Problems by Rating​

Rating 1200-1400:

  1. Round 479 Div3 - D - Divide by three, multiply by two
  2. Round 501 Div3 - D - Walking Between Houses
  3. Round 479 Div3 - E - Cyclic Components
  4. Round 686 Div3 - D - Number into Sequence
  5. Round 784 Div4 - G - Fall Down

Rating 1400-1600:

  1. Round 380 Div2 - D - Sea Battle
  2. Round 486 Div3 - E - Divisibility by 25
  3. Round 535 Div3 - D - Diverse Garland
  4. Round 693 Div3 - E - Correct Placement
  5. Round 661 Div3 - E - Find the Car

Rating 1600-1800:

  1. Round 348 Div2 - D - Little Artem and Dance
  2. Round 479 Div3 - F - Consecutive Subsequence
  3. Round 290 Div2 - D - Fox And Jumping
  4. Round 632 Div2 - D - Challenges in school №41
  5. Round 427 Div2 - D - Misha, Grisha and Underground

Rating 1800-2000:

  1. Round 392 Div2 - D - Arpa's weak amphitheater and Mehrdad's valuable Hoses
  2. Round 402 Div2 - D - String Game
  3. Round 363 Div2 - D - Fix a Tree
  4. Round 325 Div2 - D - River Locks
  5. Round 394 Div2 - D - Dasha and Very Difficult Problem

Rating 2000-2200:

  1. Round 283 Div2 - D - Tennis Game
  2. Round 321 Div2 - D - Kefa and Dishes
  3. Round 340 Div2 - E - XOR and Favorite Number
  4. Round 256 Div2 - D - Multiplication Table
  5. Round 285 Div2 - D - Misha and Permutations Summation

Advanced CP Topics​

Parallel Binary Search:

  1. CF - Meteors
  2. CF - String Game
  3. SPOJ - MKTHNUM
  4. CF - Level Generation
  5. CF - Points, Lines and Ready-made Titles

Binary Search with Segment Trees:

  1. CF - Xenia and Bit Operations
  2. CF - Sereja and Brackets
  3. CSES - Salary Queries
  4. CF - Beautiful Numbers
  5. CF - Array Queries

Floating Point Binary Search:

  1. SPOJ - AGGRCOW
  2. CF - Weakness and Poorness
  3. SPOJ - RACE
  4. CF - Biathlon Track
  5. AtCoder - Frog 3

Binary Search + DP:

  1. CF - Levels and Regions
  2. CF - Ciel and Gondolas
  3. SPOJ - BRKSTRNG
  4. CF - Kalila and Dimna in the Logging Industry
  5. AtCoder - Slimes

Learning Timeline​

For Interview Preparation (4-5 weeks)​

Week 1: Classic Binary Search Foundation Solve all 10 problems from Phase 1. Master the basic template and understand how to avoid off-by-one errors. Practice both iterative and recursive implementations. By the end of this week, you should be able to implement binary search bug-free every time.

Week 2: Finding Boundaries Solve 10 problems from Phase 2. Learn to find first/last occurrence and handle edge cases in rotated arrays. This is crucial for many real-world applications.

Week 3: Binary Search on Answer - Core Pattern Solve all 10 problems from Phase 3. This is THE most important pattern for interviews. Learn to identify when you can binary search on the answer space. Understand the "check" function pattern.

Week 4: 2D Search and Advanced Applications Solve 8 problems from Phase 4 and start Phase 5. Learn to apply binary search in 2D spaces and combine it with other techniques.

Week 5: Review and Mixed Practice Complete remaining problems from Phase 5 and 6. Do mock interviews. Time yourself. Practice explaining your approach clearly. Review problems where you struggled.

For Competitive Programming (3-4 months)​

Month 1: Strong Foundation Complete all CSES binary search problems. Solve AtCoder problems 1-10. Practice Codeforces 1200-1400 rated problems. Master both iterative and recursive templates. Target 40-50 problems this month.

Month 2: Intermediate Patterns Complete remaining AtCoder problems. Solve Codeforces 1400-1700 rated problems. Learn binary search with prefix sums, sliding window, and greedy. Target 40-50 problems.

Month 3: Advanced Applications Master parallel binary search. Learn binary search with segment trees. Practice floating point binary search. Solve 1700-1900 rated problems. Target 30-40 problems.

Month 4: Mastery and Speed Combine binary search with DP and other advanced techniques. Practice on 1900+ rated problems. Participate in virtual contests. Focus on recognizing binary search opportunities quickly. Target 25-30 problems.

Common Binary Search Patterns​

1. Classic Binary Search - Finding element in sorted array. Basic template.

2. Finding Boundaries - First/last occurrence, lower_bound/upper_bound. Use left/right bias.

3. Binary Search on Answer - Minimize maximum or maximize minimum. Define check function.

4. Rotated Array Search - Find pivot or search in rotated array. Compare with boundaries.

5. 2D Binary Search - Search in row-sorted or column-sorted matrices. Reduce dimensions.

6. Parallel Binary Search - Multiple queries with binary search. Optimize with offline processing.

7. Floating Point Binary Search - Continuous search space. Use precision-based loop.

8. Binary Search + Greedy - Check function uses greedy algorithm. Common in optimization.

9. Binary Search + DP - Optimize DP with binary search. Convex hull trick applications.

10. Implicit Binary Search - Search space not explicitly given. Derive from constraints.

Identifying Binary Search Problems​

A problem likely uses binary search if:

  • The array/list is sorted (or can be sorted)
  • You're looking for a specific value or boundary
  • You need to optimize something with monotonic property
  • "Minimize maximum" or "Maximize minimum" appears
  • Time limit suggests better than O(n²) is needed

Keywords that often indicate binary search:

  • "Sorted array"
  • "Find minimum/maximum satisfying"
  • "At least/at most K"
  • "Smallest/largest value such that"
  • "Optimize" with monotonic constraints

Not every sorted array problem needs binary search - sometimes two pointers or sliding window is better.

Final Thoughts​

Binary Search appears simple but mastering it requires understanding multiple patterns and handling edge cases flawlessly. The progression from basic search to binary search on answer is crucial.

For interviews, focus on the three main templates and practice recognizing when to apply each one. Solve 50-60 problems across all patterns and you'll be well-prepared. The key is being able to implement bug-free and explain your approach clearly.

For competitive programming, you need to recognize binary search opportunities in problems that don't explicitly mention it. Practice formulating check functions for novel problems. Master parallel binary search and combining binary search with other techniques.

Remember: Binary search is about reducing search space by half repeatedly. If you can define what you're searching for and the space has monotonic property, binary search is likely applicable.

The first 20 problems might feel challenging, but after 50 problems, you'll start recognizing patterns instantly. Binary search becomes one of your strongest tools.