java分块查找(8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87)

Java 分块查找（Block Search）是一种查找算法，它将待查找的数据按照一定的规则分为若干块，每一块内部的数据都是有序的，然后在整个数据集合中进行查找。该算法的时间复杂度为 O(√n)。

以下是 Java 分块查找的实现代码：

public static int blockSearch(int[] arr, int target) {
    int blockSize = (int) Math.sqrt(arr.length); // 每块大小
    int blockIndex = target / blockSize; // 目标值所在块的索引
    int start = blockIndex * blockSize; // 目标值所在块的起始索引
    int end = Math.min((blockIndex + 1) * blockSize - 1, arr.length - 1); // 目标值所在块的结束索引
    for (int i = start; i <= end; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1; // 没有找到
}

将给定数组按照块的大小划分为若干块，再在每一块内部使用线性查找进行查找，直到找到目标值或者遍历完所有块。例如，对于给定数组 {8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87}，若要查找目标值为 38，先计算每块大小为 5，目标值所在块的索引为 7，起始索引为 35，结束索引为 39。在该块内部进行线性查找，找到目标值。因此，该算法的时间复杂度为 O(√24) ≈ O(5)。