Back to Searching

Block Search Visualizer

Watch how Block Search divides the array into blocks and performs linear search within the appropriate block.

Time: O(√n)
Space: O(1)
Requirement: Sorted Array
Block + Linear
Block Size: √16 = 4 | Phase: SETUP | Comparisons: 0
0
1
START
1
3
2
5
3
7
4
9
5
11
6
13
7
15
8
17
9
19
10
21
11
23
12
25
13
27
14
29
15
31
Target: 13 | Step: 1 of 0

Current Step:

Click Start to begin Block Search visualization

Block Search

Time Complexity:O(√n)
Space Complexity:O(1)
Block Size:√n
Type:Hybrid

Color Legend

Currently Checking
Current Block
Target Found
Not in Current Block

vs Jump Search

Block Search:Fixed block size
Jump Search:Variable jump size
Both:O(√n) complexity

Block search is conceptually simpler and easier to implement than jump search.

How It Works

  1. 1Divide array into blocks of size √n
  2. 2Find block containing the target
  3. 3Perform linear search within block
  4. 4Return index if found, -1 otherwise

Python Implementation

import math

def block_search(arr, target):
    n = len(arr)
    block_size = int(math.sqrt(n))
    block_start = 0
    
    # Find the appropriate block
    while block_start < n:
        block_end = min(block_start + block_size - 1, n - 1)
        
        if arr[block_end] >= target:
            # Linear search within the block
            for i in range(block_start, block_end + 1):
                if arr[i] == target:
                    return i
                elif arr[i] > target:
                    return -1
            return -1
        
        block_start += block_size
    
    return -1

Real-world Applications

  • • Simple alternative to jump search
  • • Educational purposes for algorithm study
  • • Memory block organization
  • • File system block searching
  • • Cache-friendly data structure searches
  • • When simplicity over optimization matters