Block Search

Color Legend

vs 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