DSAverse
Searching Algorithms
Loading Searching Algorithms...
Search Visualization
3
9
14
21
28
35
47
56
63
72
sorted arrayindex 0
Initializing Sorting Algorithms...
Sorting
Trees
Graphs
Preparing interactive visualizations...
Searching Algorithms
Loading Searching Algorithms...
Search Visualization
Also known as Jump Search — scan block endpoints by sqrt(n) jumps, then linear search within the block.
Press Play to start the visualization.
Block search (also called Jump Search) divides the sorted array into blocks of size sqrt(n). Phase 1 scans block endpoints by jumping sqrt(n) steps at a time. Phase 2 does a linear scan within the identified block.
The sqrt(n) block size is optimal: it minimizes total comparisons since both phases take at most sqrt(n) comparisons each, giving O(sqrt(n)) overall.
It sits between linear search O(n) and binary search O(log n) in complexity, but has the advantage of traversing the array in a forward direction, which can benefit cache performance.
What is the optimal block size used in block search?