关于查找的常见算法

什么是查找

在一些（有序的/无序的）数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程叫做查找。即根据给定的某个值，在查找表中确定一个关键字等于给定值的记录或数据元素。

查找算法分类

静态查找与动态查找
- 静态查找：数据集合稳定，在查找的过程中，不需要增加、删除元素的查找操作
- 动态查找：数据集合进行查找的过程中，需要同时添加或删除元素的查找操作
无序查找与有序查找
- 无序查找：被查找数列有序无序均可
- 有序查找：被查找数列必须为有序数列

平均查找长度（Average Search Length，ASL）：需和指定 key 进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。

对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi * Ci 的和

Pi：查找表中第 i 个数据元素
Ci：找到第 i 个数据元素时已比较过的次数

常见的静态查找

对于静态查找，常用的查找算法有顺序查找，如果数据集合是有序排列的，则可以使用二分查找、黄金分割查找算法等来提高查找的效率。

顺序查找

顺序查找适合于存储结构为顺序存储或链接存储的线性表。顺序查找也叫线性查找，属于无序查找算法

查找的过程

从表中的第一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功。如果查找了所以的记录仍然找不到与给定值相等的关键字，则查找不成功。

时间复杂度：O(n)

代码实现

int search(int arr[], int length, int item) {
    for (int i = 0; i < length; i++) {
        if (arr[i] == item) {
            return i;
        }
    }
    return -1;
}

二分查找

元素必须是有序的，如果是无序的则要先进行排序操作。也称为折半查找，属于有序查找算法

查找的过程

用给定值 k 先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据 k 与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

时间复杂度：O($log_2n$)

例如：长度为10的有序表的平均查找长度为：$ASL = (1 \times 1 + 2 \times 2 + 3 \times 4 + 4 \times 3 ) / 10 = 2.9$

折半查找的前提条件是需要有序表顺序存储（即顺序表），对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。——《大话数据结构》

代码实现

int binarySerch(int arr[], int length, int target) {
    int low = 0;
    int high = length - 1;
    while (low < high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target) {
            return mid;
        }else if(target > arr[mid]) {
            low += 1;
        }else {
            high -=1;
        }
    }
    return -1;
}

// 递归
int reBinarySerch(int arr[], int target, int low, int high) {
    if (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid;
        }else if (arr[mid] > target) {
            return reBinarySerch(arr, target, low, high - 1);
        }else {
            return reBinarySerch(arr, target, low + 1, high);
        }
    }else return -1;
}

插值插值

在介绍插值查找之前，先来看一个问题，为什么二分查找一定要折半，而不是四分之一或者折更多呢？举个例子，在字典中，查『apple』，你下意识翻开字典是翻开前面的书页还是后面的书页呢？如果再让你查『zoo』，你又怎么查？很显然，这里你绝对不会从中间开始查找，而是有一定目的的往前或往后翻。

同样的，要在 1~10000 之间的 100 个元素从小到大均匀分别的数列中查找 5，自然会考虑从书中下标较小的开始查找。

综上分析，折半查找这种查找方式，不是自适应的，二分查找中查找点计算如下：$mid = (low + high) / 2$，即$mid = low + (high - low) / 2$

通过类比，我们可以将查找点计算改进为：

$mid = low + \frac{key - arr[low]} {arr[high] - arr[low]} * (high - low)$

也就是将上诉的比例参数 1/2 改进为自适应的，根据关键字在整个有序表中所处的位置，让 mid 值的变化更靠近关键字 key，从而减少比较次数

时间复杂度：$O(log_2(log_2n))$

代码实现

int insertionSearch(int arr[], int target, int low, int high) {
    if (low <= high) {
        int mid = low + (low + high) * (target - arr[low]) / (arr[high] - arr[low]) ;
        if (arr[mid] == target) {
            return mid;
        }else if (arr[mid] > target) {
            return insertionSearch(arr, target, low, high - 1);
        }else {
            return insertionSearch(arr, target, low + 1, high);
        }
    }else return -1;
}

斐波拉契查找

在介绍斐波拉契查找算法之前，先来了解一下和它紧密相关的熟知的概念——黄金分割

黄金比例又称为黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为 1 : 0.618 或 1.168 : 1

在斐波拉契数列的递增中，前后两个数的比值会越来越接近 0.618，利用这个特性，就可以将黄金比例运用到查找中

基本思想：二分查找的一种提升算法，通过运用黄金分割比例的概念在数列中选择查找点进行查找，提高查找效率。同样的，斐波拉契查找也属于一种有序查找算法

比较结果分为三种：

相等，mid 位置的元素即为所求
大于，low = mid + 1，k = k - 2
- low = mid + 1是指待查找的元素在[mid+1，high]范围内，k = k - 2说明范围[mid+1，high]内的元素个数为 n - (F(k-1)) = Fk-1 - F(k - 1) = Fk - F(k - 1) - 1 = F(k - 2) - 1个
小于，low = mid - 1，k = k - 1
- low = mid - 1是指待查找的元素在[low, mid - 1]范围内，k = k - 1说明范围[low, mid - 1]内的元素个数为 F(k-1)-1个

时间复杂度：$O(log_2n)$

代码实现

#define MAXSIZE 20
void Fibonacci(int *F) {
    F[0] = 0;
    F[1] = 1;
    for (int i = 2; i < MAXSIZE; i++) {
        F[i] = F[i - 1] + F[i - 2];
    }
}

int FibonacciSearch(int *arr, int length, int target) {
    int low = 0;
    int higt = length - 1;
    int F[MAXSIZE];
    // 构造一个斐波那契数组F
    Fibonacci(F);
    
    // 计算n位于斐波那契数列的位置
    int k = 0;
    while (length > F[k] - 1) {
        ++k;
    }
    
    // 将数组arr扩展到F[k]-1的长度
    for (int i = length; i < F[k] - 1; i++) {
        arr[i] = arr[length];
    }
    
    while (low <= higt) {
        int mid = low + F[k - 1] - 1;
        if (target < arr[mid]) {
            higt = mid - 1;
            k -= 1;
        }else if (target > arr[mid]) {
            higt = mid + 1;
            k -= 2;
        }else {
            if (mid < length) {
                // 若相等则说明mid即为查找到的位置
                return mid;
            }else {
                // 若mid>=length则说明是扩展的数值,返回length-1
                return length - 1;
            }
        }
    }
    
    return -1;
}

动态查找

二叉查找树

二叉查找树（Binary Search Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree）或是一棵空树，或者是具有以下性质的二叉树：

若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值
若任意结点的右子树不空，则右子树上所有结点的值均大于它的根结点的值
任意结点的左右子树也分别为二叉查找树

二叉查找树性质：对二叉查找树进行中序遍历，即可得到有序的数列

结点结构设计

typedef struct BitNode{
    int data;
    struct BitNode *leftTree, *rightTree;
}BitNode, *BitTree;

二叉查找树的查找

BitTree searchBST(BitTree T, int target) {
    while (T != NULL && T->data != target) {
        if (target < T->data) {
            T = T->leftTree;
        }else {
            T = T->rightTree;
        }
    }
    return T;
}

// 递归
BitTree reSearchBST(BitTree T, int target) {
    if (T == NULL || target == T->data) {
        return T;
    }
    if (target < T->data) {
        return reSearchBST(T->leftTree, target);
    }else {
        return reSearchBST(T->rightTree, target);
    }
}

二叉查找树的插入

插入结点时，需要先判断当前二叉查找树中是否存在 key

如果存在，不插入
当不存在 key 时，需要插入，同时插入需要保证二叉查找树的性质规则

void insertBST(BitTree *T, int target) {
    BitTree node, temp = NULL;
    if (searchBST(*T, target) == NULL) {
        // 查找失败，插入结点
        node = (BitTree)malloc(sizeof(BitNode));
        node->data = target;
        node->leftTree  = NULL;
        node->rightTree = NULL;
        if (*T == NULL) {
            *T = node;
        }else {
            temp = *T;
            BitTree pre = temp;
            while (temp != NULL) {
                pre = temp;
                if (target < temp->data) {
                    temp = temp->leftTree;
                }else {
                    temp = temp->rightTree;
                }
            }
            if (pre->data > target) {
                pre->leftTree = node;
            }else {
                pre->rightTree = node;
            }
        }
    }
}

二叉查找树的删除

删除结点是二叉查找树最复杂的一个地方，主要是由于删除的时候，存在很多情况

被删除的结点没有左右子树
被删除的结点只有左子树
被删除的结点只有右子树
被删除的结点有左右子树

对于前三种情况比较好处理，直接令其父亲指向其孩子即可；最后一种则比较复杂，首先，在二叉查找树中序遍历，可以换得到有序的序列。因此，可以选择按照中序遍历，选取待删除结点的前一个结点或下一个结点，来取代待删除的结点位置。

int delete(BitTree *T) {
    BitTree temp, node;
    if ((*T)->rightTree == NULL) {
        temp = *T;
        (*T) = (*T)->leftTree;
        free(temp);
    }else if ((*T)->leftTree == NULL) {
        temp = *T;
        (*T) = (*T)->rightTree;
        free(temp);
    }else {
        temp = *T;
        node = (*T)->leftTree;

        // 将 node 指向右子树的尽头（目的是找到待删除结点的前驱）
        // 在删除结点的左子树中，从右边找到直接前驱
        // 用 temp 保存直接前驱的双亲结点
        while (node->rightTree) {
            temp = node;
            node = node->rightTree;
        }
        
        // 将待删除结点的数据更新为 node 的数据
        (*T)->data = node->data;
        
        // 重连子树
        // 如果 temp 不等于 p, 则将 node 的左子树赋值给 temp 的右子树
        // 如果 temp 等于 p, 则将 node 的左子树赋值给 temp 的左子树
        if (temp != (*T)) {
            temp->rightTree = node->leftTree;
        }else {
            temp->leftTree = node->leftTree;
        }
        free(node);
    }
    return 1;
}

int deleteBST(BitTree *T, int target) {
    if (*T == NULL) {
        return -1;
    }else {
        if ((*T)->data == target) {
            return delete(T);
        }else if (target < (*T)->data) {
            return deleteBST(&(*T)->leftTree, target);
        }else {
            return deleteBST(&(*T)->rightTree, target);
        }
    }
}

平衡二叉树

总结

完整代码