c++实现 顺序查找、折半查找和分块查找

顺序查找：

int seq_search(int arr[], int len, int key) {
    for (int i = 0; i < len; i++) {
        if (arr[i] == key) {
            return i;
        }
    }
    return -1;
}

折半查找：

int binary_search(int arr[], int len, int key) {
    int left = 0, right = len - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == key) {
            return mid;
        } else if (arr[mid] < key) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

分块查找：

const int BLOCK_SIZE = 3;

struct Block {
    int l, r, max_val;
};

Block blocks[(int)ceil(1.0 * N / BLOCK_SIZE)];
int block_cnt, arr[N + 5];

void build_blocks(int n) {
    block_cnt = (int)ceil(1.0 * n / BLOCK_SIZE);
    for (int i = 1; i <= block_cnt; i++) {
        blocks[i].l = (i - 1) * BLOCK_SIZE + 1;
        blocks[i].r = min(i * BLOCK_SIZE, n);
        blocks[i].max_val = -1;
        for (int j = blocks[i].l; j <= blocks[i].r; j++) {
            blocks[i].max_val = max(blocks[i].max_val, arr[j]);
        }
    }
}

int block_search(int n, int key) {
    int block_id = 1;
    while (block_id <= block_cnt && blocks[block_id].max_val < key) {
        block_id++;
    }
    if (block_id > block_cnt) {
        return -1;
    }
    for (int i = blocks[block_id].l; i <= blocks[block_id].r; i++) {
        if (arr[i] == key) {
            return i;
        }
    }
    return -1;
}

注意，以上实现中的 `N` 为数据规模，可以根据具体情况进行修改。