python分块查找算法

分块查找算法是一种基于顺序查找的算法，它将一个大的无序列表分成若干个块，每个块内部有序，块与块之间无序。这样可以通过先对块进行二分查找，找到目标元素所在的块，然后再在该块内部进行顺序查找，从而提高查找效率。下面是Python实现分块查找算法的示例代码：

import math

def block_search(arr, target):
    block_size = int(math.sqrt(len(arr))) # 计算块的大小
    for i in range(0, len(arr), block_size):
        if arr[i] > target: # 如果当前块的第一个元素已经大于目标元素，说明目标元素不存在
            return -1
        if i + block_size < len(arr): # 如果当前块不是最后一个块
            if arr[i + block_size - 1] < target: # 如果当前块的最后一个元素小于目标元素，说明目标元素可能在下一个块中
                continue
            else: # 否则在当前块中进行顺序查找
                for j in range(i, i + block_size):
                    if arr[j] == target:
                        return j
        else: # 如果当前块是最后一个块
            for j in range(i, len(arr)):
                if arr[j] == target:
                    return j
            return -1 # 如果最后一个块中也没有找到目标元素，说明目标元素不存在