静态查找表

顺序查找

时间复杂度$O(n)$

int sequential_search(int arr[], int length, int key) {
    for (int i = 0; i < length; i++) {
        if (arr[i] == key)
            return i; // 找到返回索引
    }
    return -1; // 未找到返回 -1
}

二分查找

标准二分查找

时间复杂度$O(\log n)$

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

传入low、high

int BinarySearch(int arr[], int key, int low, int high) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == key)
            return mid;
        else if (arr[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}

优点：

  • 查找时间效率较高 缺点：
  • 查找表记录按照关键字的值有序排列
  • 只适用于有序连续顺序表

插值查找

时间复杂度$O(\log(\log n))$

int inter_search(int arr[], int length, int key)
{
    int left = 0, right = length - 1, m;
    while (left <= right && arr[left] != arr[right]) {
        m = left + ((right - left) * (key - arr[left])) / (arr[right] - arr[left]);
        if (m < left || m > right)
            break;
        if (key < arr[m])
            right = m - 1;
        else if (key > arr[m])
            left = m + 1;
        else
            return m;
    }
    if (arr[left] == key)
        return left;
    return -1;
}

斐波那契查找

时间复杂度$O(\log n)$

int FibonacciSearch(int arr[], int length, int key) {
    // 初始化斐波那契数列
    int fibMMm2 = 0;   // F(k-2)
    int fibMMm1 = 1;   // F(k-1)
    int fibM = fibMMm2 + fibMMm1; // F(k)

    // 找到第一个大于等于 length 的斐波那契数
    while (fibM < length) {
        fibMMm2 = fibMMm1;
        fibMMm1 = fibM;
        fibM = fibMMm2 + fibMMm1;
    }
    int offset = -1;
    while (fibM > 1) {
        int i = (offset + fibMMm2 < length - 1) ? offset + fibMMm2 : length - 1;
        if (arr[i] < key) {
            fibM = fibMMm1;
            fibMMm1 = fibMMm2;
            fibMMm2 = fibM - fibMMm1;
            offset = i;
        } else if (arr[i] > key) {
            fibM = fibMMm2;
            fibMMm1 = fibMMm1 - fibMMm2;
            fibMMm2 = fibM - fibMMm1;
        } else {
            return i;
        }
    }
    // 检查最后一个元素
    if (fibMMm1 && offset + 1 < length && arr[offset + 1] == key)
        return offset + 1;
    return -1;
}

索引查找

时间复杂度$O(\sqrt{n})$

typedef struct {
    int key;    // 索引关键字
    int pos;    // 主表起始位置
} Index;

int index_sequential_search(int arr[], int length, Index index[], int indexLen, int key) {
    int i = 0;

    // 找到 key 所在的区间
    while (i < indexLen && key > index[i].key)
        i++;

    // 确定搜索区间
    int start = (i == 0) ? 0 : index[i - 1].pos;
    int end = (i < indexLen) ? index[i].pos : length;

    // 顺序查找
    for (int j = start; j < end; j++) {
        if (arr[j] == key)
            return j;
    }

    return -1;
}

动态查找表

二叉查找树

树节点结构

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node, *Nodeptr;
  1. 查找操作 时间复杂度O(h),h是树的高度
Nodeptr searchBST(Nodeptr bstree, int key) {
    if (bstree == NULL || bstree->data == key)
        return bstree;
    if (key < bstree->data)
        return searchBST(bstree->left, key);
    else
        return searchBST(bstree->right, key);
}
  1. 插入操作
Nodeptr createNode(int data) {
    Nodeptr newNode = (Nodeptr)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 插入节点到BST
Nodeptr insertBST(Nodeptr root, int data) {
    if (root == NULL)
        return createNode(data);
    if (data < root->data)
        root->left = insert(root->left, data);
    else if (data > root->data)
        root->right = insert(root->right, data);
    return root;
}
  1. 删除操作
Nodeptr deleteBST(Nodeptr root, int key) {
    if (root == NULL) return NULL;

    if (key < root->data)
        root->left = deleteNode(root->left, key);
    else if (key > root->data)
        root->right = deleteNode(root->right, key);
    else {
        // 找到目标节点
        if (root->left == NULL) {
            Nodeptr temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            Nodeptr temp = root->left;
            free(root);
            return temp;
        } else {
            // 两个子节点：找右子树最小值替代
            Nodeptr minNode = root->right;
            while (minNode->left != NULL)
                minNode = minNode->left;
            root->data = minNode->data;
            root->right = deleteNode(root->right, minNode->data);
        }
    }
    return root;
}