Binary Search —
Eliminate half. Every single step.
Binary search finds a target in a sorted array in O(log n) — not by checking every element, but by eliminating half the remaining elements at each step. With 1 million elements, it takes at most 20 comparisons. Watch left, mid, and right collapse toward the answer on LearnBug and the logic becomes impossible to forget.
What is Binary Search?
Binary search works on a sorted array by repeatedly halving the search space. You start with the full array, compute the midpoint, and compare the middle element to your target. If it matches — done. If the target is smaller, ignore the right half. If larger, ignore the left half. Repeat on the remaining half until found or the search space is empty.
Why visualization changes everything
The off-by-one errors in binary search are legendary — mid + 1 vs mid, < vs <=. On LearnBug you see exactly which elements are still in play at each step, where mid lands, and which half gets eliminated. The boundary conditions stop being confusing the moment you watch them in action.
Finding target 7 in a sorted array
Array: [1, 3, 5, 7, 9, 11, 13] — target: 7. Watch the search space halve each step.
Initialise — left = 0, right = 6
Full array in play. Compute mid = (0 + 6) // 2 = 3. Element at index 3 is 7. That's our target — found in one step! Let's trace a harder case where it takes more steps.
Target = 11 — mid (7) is too small, go right
nums[mid] = 7 < 11. Target must be in the right half. Set left = mid + 1 = 4. Left half eliminated — never look at it again.
New mid = (4 + 6) // 2 = 5
nums[5] = 11. That's our target! Return index 5. Total comparisons: 2. For a 7-element array, O(log 7) ≈ 2.8 — exactly right.
When does it return -1? Left crosses right.
If the target doesn't exist, left eventually exceeds right. The loop condition while left <= right fails and we return -1. This is the exit condition — when left and right cross, the search space is empty.
left > right → return -1 (not found)
Clean binary search implementation
def binary_search(nums, target):
left = 0
right = len(nums) - 1
while left <= right: # ← <= not < (handles 1-element array)
mid = left + (right - left) // 2 # ← avoids integer overflow
if nums[mid] == target:
return mid # found
elif nums[mid] < target:
left = mid + 1 # go right
else:
right = mid - 1 # go left
return -1 # not founddef binary_search_recursive(nums, target, left, right):
if left > right:
return -1 # base case — not found
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
return binary_search_recursive(nums, target, mid + 1, right)
else:
return binary_search_recursive(nums, target, left, mid - 1)Time & Space Complexity
The 3 binary search bugs everyone writes
These mistakes cause infinite loops or wrong answers. Know them before your interview.
while left < right instead of <=
When only one element remains, left == right. Using < skips it entirely — you miss the answer and return -1 incorrectly.
left = mid instead of mid + 1
If mid is not the target and you set left = mid, the loop never shrinks when left == mid. Infinite loop guaranteed.
mid = (left + right) // 2 — integer overflow
In Python this is fine, but in other languages left + right can overflow. The safe formula is left + (right - left) // 2 — always use it.
Applying binary search on an unsorted array
Binary search only works when the array is sorted. If you binary search an unsorted array, mid might eliminate the half that actually contains the target.
Binary search goes beyond just "find the target"
Find First / Last Occurrence
Array has duplicates — find the leftmost or rightmost position of the target. Don't return immediately on match; instead keep searching left (or right) half to find the boundary.
Search in Rotated Sorted Array
Array is sorted but rotated at some pivot. One half is always sorted — binary search that half first to decide where the target could be.
Binary Search on Answer
The answer itself is a range — binary search on the possible answer values rather than an array. Check feasibility at each midpoint. Used in problems like "minimum days to make m bouquets".
Frequently asked questions
Why does binary search require a sorted array?
Because the elimination step relies on order. When nums[mid] < target, you conclude the target must be to the right — that's only valid if elements to the right are all larger. In an unsorted array, you'd have no idea which half to eliminate, making the algorithm incorrect.
Why is binary search O(log n) and not O(n)?
Each iteration cuts the remaining search space in half. Starting with n elements: after 1 step you have n/2, after 2 steps n/4, after k steps n/2ᵏ. You stop when n/2ᵏ = 1, which means k = log₂(n). So the maximum number of comparisons is log₂(n) — that's O(log n).
Should I use iterative or recursive binary search?
Iterative is preferred in interviews and production code. It uses O(1) space (no call stack) and avoids any risk of stack overflow on very large inputs. Recursive is cleaner to read and useful for understanding the logic, but for actual implementation, iterative wins almost every time.
What is the difference between lower bound and upper bound in binary search?
Lower bound finds the first index where the value is ≥ target (leftmost position). Upper bound finds the first index where the value is > target (one past the rightmost position). Together they give you the range of all occurrences of the target in an array with duplicates. Python's bisect_left is lower bound and bisect_right is upper bound.
Can binary search be used on a linked list?
Technically yes, but it's impractical. Binary search requires O(1) random access to compute and jump to the midpoint. On a linked list, finding the midpoint takes O(n) each time, making the total complexity O(n log n) — worse than just scanning linearly. Binary search is designed for arrays with index-based access.
Watch left, mid, and right collapse on your own array
Paste your binary search problem into LearnBug and see every elimination step animated.