常见的查找算法汇总（含详细代码）5

test.c

/**
 * C语言实现的红黑树(Red Black Tree)
 *
 * @author skywang
 * @date 2013/11/18
 */


#include 
#include "rbtree.h"


#define CHECK_INSERT 0    // "插入"动作的检测开关(0，关闭；1，打开)
#define CHECK_DELETE 0    // "删除"动作的检测开关(0，关闭；1，打开)
#define LENGTH(a) ( (sizeof(a)) / (sizeof(a[0])) )


void main()
{
    int a[] = {10, 40, 30, 60, 90, 70, 20, 50, 80};
    int i, ilen=LENGTH(a);
    RBRoot *root=NULL;


    root = create_rbtree();
    printf("== 原始数据: ");
    for(i=0; i

7、分块查找

7.1、基本原理

分块查找（Block Search）是一种基于分块思想的查找算法。它将待查找的数据集合分成多个块（Block），每个块内的数据按照某种方式有序排列。这样就可以在查找时快速缩小查找范围，从而提高查找效率。

分块查找的基本原理如下：

1. 将待查找的数据分成若干块，并将每块内的数据按照某种方式有序排列。
2. 确定各块的范围和关键字，用一张索引表来存放各块的关键字和起始地址。
3. 查找时，先在索引表中二分查找到关键字所在的块，然后在该块内进行线性查找，直到找到目标数据。

分块查找的注意事项和应用场景如下：

1. 数据分块要尽量均匀，使每块数据量大致相等。
2. 对每个块内的数据要按照某种方式有序排列，以便进行二分查找。
3. 适合数据集合变动较少的情况，如果数据频繁变动，需要不断重构索引表，效率较低。
4. 分块查找适合于数据量较大，但又不适合全部加载到内存中的情况，比如外部文件查找。

7.2、代码示例

#include 


// 定义块的大小
#define BLOCK_SIZE 3


// 分块查找函数
int blockSearch(int arr[], int n, int key)
{
    // 计算块的数量
    int blockCount = (n + BLOCK_SIZE - 1) / BLOCK_SIZE;


    // 创建一个块数组，存储每个块的最大值
    int blockMax[blockCount];
    for (int i = 0; i < blockCount; i++) {
        int max = arr[i * BLOCK_SIZE];
        for (int j = 1; j < BLOCK_SIZE && i * BLOCK_SIZE + j < n; j++) {
            if (arr[i * BLOCK_SIZE + j] > max) {
                max = arr[i * BLOCK_SIZE + j];
            }
        }
        blockMax[i] = max;
    }


    // 在块数组中查找key所在的块
    int blockIndex = 0;
    while (blockIndex < blockCount && blockMax[blockIndex] < key) {
        blockIndex++;
    }


    // 在块中进行线性查找
    int startIndex = blockIndex * BLOCK_SIZE;
    int endIndex = startIndex + BLOCK_SIZE;
    for (int i = startIndex; i < endIndex && i < n; i++) {
        if (arr[i] == key) {
            return i;
        }
    }


    return -1;
}


int main()
{
    int arr[] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    int n = sizeof(arr) / sizeof(arr[0]);


    int key = 12;
    int index = blockSearch(arr, n, key);
    if (index == -1) {
        printf("%d not found\\n", key);
    } else {
        printf("%d found at index %d\\n", key, index);
    }


    return 0;
}

该程序定义了一个 BLOCK_SIZE 常量，表示块的大小。在分块查找函数中，首先计算块的数量，然后创建一个块数组，存储每个块的最大值。接下来，在块数组中查找key所在的块，并在该块中进行线性查找。如果找到了key，则返回其下标，否则返回-1。最后，程序使用一个示例数组来测试分块查找函数，查找数组中的一个元素并输出结果。