Binary Search
The Binary Search Pattern
Halve the search space on every comparison. The powerful form in interviews is not searching a sorted array but binary searching the answer itself: guess a value, ask a yes/no feasibility question, and discard half the range of possible answers.
Interactive problems
Free to open
How do you recognise a binary search problem?
The data is sorted or rotated-sorted, or — more often — the answer lies in a numeric range and there is a monotonic feasibility check ("if capacity C works, C+1 also works"). "Minimum capacity to ship packages in D days" is binary search on the answer.
What is the time complexity of the binary search pattern?
O(log n) per search. Binary searching an answer range costs O(log(range) × cost of the feasibility check).
Binary Search practice problems
Each problem pairs a worked explanation with an interactive visualizer you step through yourself, plus the implementation in JavaScript, Python, Java and C++.
Binary Search problems by difficulty and complexity
The difficulty, running time and extra space of every binary search solution on this page, as each lesson derives them.
| Lesson | Difficulty | Best | Average | Worst | Space |
|---|---|---|---|---|---|
| Binary Search | Easy | Ω(1) | Θ(log n) | O(log n) | O(1) |
| Apple Harvest (Koko Variant) | Medium | Ω(n log M) | Θ(n log M) | O(n log M) | O(1) |
| Search in Rotated Sorted Array | Medium | Ω(1) | Θ(log n) | O(log n) | O(1) |
Related patterns and concepts
The underlying technique is covered from first principles in the binary search lesson in the DSA visualizer curriculum. Binary Search is one of the 17 coding interview patterns, and its problems also appear in the DSA 75 interview sprint.
Every other coding interview pattern
Depth-First Search · 25 lessons
- Introduction to DFSFree
- DFS FundamentalsFree
- Return Values in DFS
- Invert Binary Tree
- Maximum Depth of Binary Tree
- Path Sum
- Passing Values Down (State)
- Validate Binary Search Tree
- Kth Smallest Element in a BST
- Construct Binary Tree from Preorder and Inorder Traversal
- Binary Tree Tilt
- Diameter of Binary Tree
- Lowest Common Ancestor of a Binary Tree
- Path Sum II
- Longest Univalue Path
- Graphs Overview
- Graph Representation: Adjacency List
- Clone Graph
- Graph Valid Tree
- Matrices as Graphs
- Flood Fill
- Types of DFS (Tree Traversals)
- Number of Islands
- Surrounded Regions
- Pacific Atlantic Water FlowFree