DSAverse

Searching Algorithms

Loading Searching Algorithms...

Search Visualization

sorted arrayindex 0

Binary Search

Repeatedly halve the search space by comparing the target with the middle element. Requires a sorted array but finds in O(log n) — the gold standard for sorted data.

Visualization

Target:

Speed

Midpoint (M)FoundSearch rangeEliminated

Target

Comparisons

1/0

Step

Ready — press Play or step through.

Complexity

O(1)

Best Case

O(log n)

Worst Case

O(log n)

Average

O(1)

Space

How It Works

1Set left=0, right=n-1 (entire array in range)
2Compute mid = floor((left + right) / 2)
3If arr[mid] == target: done. If arr[mid] < target: left = mid+1. Else: right = mid-1
4Repeat until left > right (not found) or target located

Applications

•Database index lookups (B-tree search)
•Standard library: Python bisect, Java Arrays.binarySearch
•Finding insertion points in sorted lists
•Answer binary search (search on answer space, not array)

Active Recall Quiz

Question 1 of 3

What precondition is required for binary search to work correctly?

DSAverse

Searching Algorithms

Loading Searching Algorithms...

Search Visualization

sorted arrayindex 0