Efficiently find an element in a sorted array by repeatedly halving the search space.
Parameters
15
Visualization
Step: 0
Enter a target and click Step or Auto-Run.
Algorithm Insight
Binary Search is a Divide and Conquer algorithm.
1.Find the middle bar of the active search range.
2.If $MidHeight = Target$, search complete!
3.If $Target < Mid$, discard everything to the right.
4.If $Target > Mid$, discard everything to the left.
Efficiency
Time ComplexityO(log N)
Space ComplexityO(1)
Binary Search: The Power of Halving
Explore how "divide and conquer" makes searching incredibly fast. Use this guide after trying the interactive.
Quick Context: The Dictionary Analogy
Imagine finding a word in a physical dictionary. You don't start at "A" and read every word. Instead, you open it to the middle, see if your word comes before or after, and instantly eliminate half the dictionary. That is binary search. It's an algorithm that finds a target in a sorted array by repeatedly dividing the search interval in half.
The Core Idea: The Three Pointers
Binary search operates using three "pointers" or indices:
Low: Marks the beginning of the current search space. Initially, this is the first element (index 0).
High: Marks the end of the current search space. Initially, this is the last element.
Mid: The middle of the current search space, calculated as `floor((Low + High) / 2)`. This is our "guess."
The algorithm compares the element at the `Mid` index with the target value and decides which half of the array to discard.
Guided Experiments with the Visualizer
Find the Middle: Set a target value and click "Next Step". The first action is always to establish the initial `Low` and `High` pointers and then find the first `Mid`. The feedback box will explicitly state the calculation.
Discarding a Section: Click "Next Step" again. The algorithm compares the value at `Mid` to your target.
If `Target > Mid Value`, the entire left half (including `Mid`) is discarded. The `Low` pointer moves to `Mid + 1`.
If `Target < Mid Value`, the entire right half (including `Mid`) is discarded. The `High` pointer moves to `Mid - 1`.
Observe how the discarded bars are grayed out, visually representing the shrinking search space.
The "Not Found" Case: Set the target to a value you know isn't in the array (e.g., an odd number when all array values are even). Step through the algorithm. Eventually, the `Low` pointer will cross the `High` pointer (`Low > High`). This is the condition that tells the algorithm the element does not exist in the array.
Logarithmic Speed: Set the array size to its maximum (25). Notice how few steps it takes to find any element. If you double the array size, it only takes one extra step to find an element. This is the power of its O(log N) time complexity. A linear search (checking one by one) would take, on average, many more steps.
The Golden Rule & Common Pitfalls
The Golden Rule: Binary search only works on sorted data. If the array is not sorted, the fundamental assumption that you can discard half the elements is broken, and the algorithm will fail.
Off-by-One Errors: A common bug when implementing binary search is getting the `Low` and `High` updates wrong. Forgetting to do `Mid + 1` or `Mid - 1` can lead to an infinite loop if the `Mid` element is never excluded from the next search space.
Integer Overflow: In some low-level languages, calculating `(low + high) / 2` can cause an error if `low` and `high` are very large numbers. A safer way to calculate the midpoint is `low + (high - low) / 2`.
Key Takeaways
Binary search is exceptionally fast, with a time complexity of O(log N), making it ideal for large datasets.
Its main prerequisite is that the data must be sorted.
The core mechanic involves repeatedly halving the search space using `Low`, `High`, and `Mid` pointers until the target is found or the search space is empty.
Cheat sheet
Binary Search
Imagine finding a word in a physical dictionary. You don't start at "A" and read every word. Instead, you open it to the middle, see if your word comes before or after, and instantly eliminate half the dictionary. That is binary search. It's an algorithm that finds a target in a sorted array by repeatedly dividing the search interval in half.