Visual lesson
Binary Search
01
The big idea
Run it
Scrub, play, or use ← → and space.
02
Pseudocode + example
03
Complexity
| Best case | |
|---|---|
| Average case | |
| Worst case | |
| Auxiliary space |
04
Exam kit
Common trap
Quick recall
05
Video Lecture
Watch a detailed visual walkthrough by an expert educator.
06
Theoretical Q&A
Master these core conceptual questions often asked in exams.
Q1: What is the maximum number of comparisons performed by binary search on an array of size n?
The maximum number of comparisons in the worst case is floor(log₂ n) + 1. This represents the height of the decision tree. Each comparison divides the search space in half until only one candidate remains.
Q2: Why does low + (high - low) / 2 prevent integer overflow compared to (low + high) / 2?
In fixed-width integer arithmetic (such as 32-bit integers in Java or C/C++), adding two large indices low and high can exceed the maximum positive value (2,147,483,647), resulting in an overflow to a negative number. Using low + (high - low) / 2 avoids addition of the two large values and guarantees the computed sum stays within correct limits.
Q3: Can binary search be applied directly on a singly linked list? What is its time complexity?
Yes, it is possible, but highly inefficient. Finding the middle element in a singly linked list requires scanning through elements from the start, which costs O(k) time where k is the size of the sublist. Doing this iteratively yields a total time complexity of O(n) instead of O(log n), defeating the purpose of the search. A balanced Binary Search Tree or Skip List should be used instead.
?
Doubt desk
How do I reconstruct the algorithm in an exam?
- Write the state or data structure shown above.
- Write the one decision repeated in the visualization.
- Add the stopping condition.
- Count how often the repeated decision runs for complexity.