《漫画算法2：小灰的算法进阶》第四章 查找算法

什么是二分查找

二分查找算法，也称折半查找算法，是一种在有序数组中查找某一特定元素的搜索算法。它的搜索原理是将数组分成两个部分，取中间值与目标值进行比较，如果中间值等于目标值，则搜索成功；如果中间值大于目标值，则在左半部分继续搜索；如果中间值小于目标值，则在右半部分继续搜索。重复执行以上步骤，直到找到目标值或者搜索区间为空为止。

查找的时间复杂度是O(logn)

什么是跳表

跳表是一种随机化的数据结构，可以被看做二叉树的一个变种，它在性能上和红黑树，AVL树不相上下，但是跳表的原理非常简单，实质就是一种可以进行二分查找的有序链表。跳表的平均查找和插入时间复杂度都是O(logn)。跳表的查找是通过维护一个多层次的链表，且每一层链表中的元素是前一层链表元素的子集。一开始时，算法只在最上层链表进行查找，如果要查找的元素在当前链表中，则直接返回该元素；否则转到下一层链表继续查找，直到找到该元素或查找到最底层链表为止。跳表的插入和删除操作需要动态地调整链表结构，以保证跳表的性质不被破坏。

跳表是一种可以进行二分查找的有序链表，它的查找、插入、删除的时间复杂度都是O(logn)，是一种高效的数据结构。

什么是字符串匹配算法

BF算法(Brute Force)；

相比BF算法，RK算法采用了哈希值比较的方式，总的时间复杂度是O(m+n)；

RK算法的缺点在于哈希冲突，性能并不稳定。每一次出现哈希冲突的时候，RK算法都要对子串和模式串进行逐个字符的比较，如果冲突太多，RK算法就退化成了BF算法

什么是KMP算法

KMP算法的整体时间复杂度是O(m+n)，其中n是模式串的长度，m是主串长度；

算法的空间复杂度就是O(n)

小结

在有序数组中查找元素，可以使用二分查找算法，查找时间复杂度是O(logn)；

在有序链表中查找元素，可以把链表改造成跳表，查找时间复杂度是O(logn)；

BF算法是朴素的字符串匹配算法，效率较低，时间复杂度是O(m×n)；

RK算法利用hash进行字符串匹配，效率较高但不稳定，平均时间复杂度是O(m+n)；

KMP算法减少了字符串匹配过程中的无谓比较，效率较高且稳定，时间复杂度是O(m+n)