什么是二分查找

二分查找算法，也稱折半查找算法，是一種在有序數(shù)組中查找某一特定元素的搜索算法。它的搜索原理是將數(shù)組分成兩個部分，取中間值與目標值進行比較，如果中間值等于目標值，則搜索成功；如果中間值大于目標值，則在左半部分繼續(xù)搜索；如果中間值小于目標值，則在右半部分繼續(xù)搜索。重復執(zhí)行以上步驟，直到找到目標值或者搜索區(qū)間為空為止。

查找的時間復雜度是O(logn)

什么是跳表

跳表是一種隨機化的數(shù)據(jù)結構，可以被看做二叉樹的一個變種，它在性能上和紅黑樹，AVL樹不相上下，但是跳表的原理非常簡單，實質就是一種可以進行二分查找的有序鏈表。跳表的平均查找和插入時間復雜度都是O(logn)。跳表的查找是通過維護一個多層次的鏈表，且每一層鏈表中的元素是前一層鏈表元素的子集。一開始時，算法只在最上層鏈表進行查找，如果要查找的元素在當前鏈表中，則直接返回該元素；否則轉到下一層鏈表繼續(xù)查找，直到找到該元素或查找到最底層鏈表為止。跳表的插入和刪除操作需要動態(tài)地調整鏈表結構，以保證跳表的性質不被破壞。

跳表是一種可以進行二分查找的有序鏈表，它的查找、插入、刪除的時間復雜度都是O(logn)，是一種高效的數(shù)據(jù)結構。

什么是字符串匹配算法

BF算法(Brute Force)；

相比BF算法，RK算法采用了哈希值比較的方式，總的時間復雜度是O(m+n)；

RK算法的缺點在于哈希沖突，性能并不穩(wěn)定。每一次出現(xiàn)哈希沖突的時候，RK算法都要對子串和模式串進行逐個字符的比較，如果沖突太多，RK算法就退化成了BF算法

什么是KMP算法

KMP算法的整體時間復雜度是O(m+n)，其中n是模式串的長度，m是主串長度；

算法的空間復雜度就是O(n)

小結

在有序數(shù)組中查找元素，可以使用二分查找算法，查找時間復雜度是O(logn)；

在有序鏈表中查找元素，可以把鏈表改造成跳表，查找時間復雜度是O(logn)；

BF算法是樸素的字符串匹配算法，效率較低，時間復雜度是O(m×n)；

RK算法利用hash進行字符串匹配，效率較高但不穩(wěn)定，平均時間復雜度是O(m+n)；

KMP算法減少了字符串匹配過程中的無謂比較，效率較高且穩(wěn)定，時間復雜度是O(m+n)