Binary Search
Complete Binary Search Problems & Resources Guide
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.
Understanding Binary Search
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)
Phase 1: Classic Binary Search
Master the fundamental template. If you can't implement these bug-free, everything else will be difficult.
Phase 2: Finding Boundaries
Learn to find first/last occurrence and handle duplicates. This is crucial for many applications.
Phase 3: Binary Search on Answer
The most important pattern. Learning to search on the answer space rather than index space.
Phase 4: 2D Binary Search & Matrix Problems
Binary search in 2D spaces and matrix applications.
Phase 5: Advanced Binary Search on Answer
Complex applications requiring creative problem formulation.
Phase 6: Binary Search with Other Techniques
Combining binary search with greedy, DP, or other algorithms.
Competitive Programming Problems
AtCoder Binary Search Problems
CSES Binary Search Problems
Codeforces Binary Search Problems by Rating
Rating 1200-1400:
Rating 1400-1600:
Rating 1600-1800:
Rating 1800-2000:
Rating 2000-2200:
Advanced CP Topics
Parallel Binary Search:
Binary Search with Segment Trees:
Floating Point Binary Search:
Binary Search + DP:
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.