DAA 12_binary_search Divide & Conquer

Binary Search — Interactive Visual Tutorial

Binary Search works only on a sorted array. Every step compares the middle element and halves the search range.

Visualizer
Step: 0 / 0
Binary search needs sorted array. If “Auto-sort” is ON, your input will be sorted automatically.
Smaller ms = faster (e.g., 120 fast, 1000 slow).
✅ Invariant: target ∈ [low..high]
Legend Active Range low mid high found
Comparisons: 0
low
—
mid
—
high
—
A[mid]
—
Message
Enter array + target, then click Start.
Call Stack (Top = Latest) Depth: 0

Tip: Watch how the greyed-out region grows — it’s what makes Binary Search fast.

Live Pseudocode

Highlighted line matches the current step.

BinarySearch(A, target):
low = 0, high = n-1
while low <= high:
mid = ⌊(low + high)/2⌋
if A[mid] == target: return mid
else if A[mid] < target: low = mid + 1
else: high = mid - 1
return NOT_FOUND
Key idea: halving the search space every step ⇒ O(log n).
Complexity (Quick Visual)
Choose n (array size)
n = 16
Max steps (worst case)
Steps ≈ 5 (about log₂(n))
Time: O(log n)
Space: Iterative O(1), Recursive O(log n)
Quick Look
Common mistakes
• Using it on an unsorted array ❌
• Wrong loop condition: use low ≤ high
• Wrong updates: low=mid+1 and high=mid−1