跳表
因為二分查找底層依賴的是數(shù)組隨機訪問的特性，所以只能用數(shù)組來實現(xiàn)园骆。如果數(shù)據(jù)存儲在鏈表中壁袄，就真的沒法用二分查找算法了嗎？
只需要對鏈表稍加改造豆混，就可以支持類似”二分“的查找算法篓像。把改造之后的數(shù)據(jù)結(jié)構(gòu)叫做跳表（Skip list）。
如何理解跳表
對于一個單鏈表來講皿伺，即便鏈表中存儲的數(shù)據(jù)是有序的员辩，如果要想在其中查找某個數(shù)據(jù)，也只能從頭到尾遍歷鏈表鸵鸥。這樣查找效率就會很低奠滑，時間復(fù)雜度會很高，是O(n)脂男。
那怎么來提高查找效率呢养叛？如果像圖中那樣，對鏈表建立一級”索引“宰翅，查找起來是不是就會更快一些呢？每兩個結(jié)點提取一個結(jié)點到上級爽室，把抽出來的哪一級叫做索引或索引層汁讼。圖中的down表示down指針，指向下一級結(jié)點阔墩。
如果現(xiàn)在要查找某個結(jié)點嘿架，比如16⌒ン铮可以先在索引層遍歷耸彪，當(dāng)遍歷到索引層中值為13的結(jié)點時，發(fā)現(xiàn)下一個結(jié)點是17忘苛，那要查找的結(jié)點16肯定就在這兩個結(jié)點之間蝉娜。然后通過索引層結(jié)點的down指針，下降到原始鏈表這一層扎唾，繼續(xù)遍歷召川。這個時候，只需要再遍歷2個結(jié)點胸遇，就可以找到值等于16的這個結(jié)點了荧呐。這樣，原來如果要查找16，需要遍歷10個結(jié)點倍阐，現(xiàn)在只需要遍歷7個結(jié)點概疆。
從這個例子中，可以看出峰搪，加上一層索引之后届案，查找一個結(jié)點需要遍歷的結(jié)點個數(shù)減少了，也就是說查找效率提高了罢艾。那如果再加一層索引呢楣颠，效率會不會提升更多呢？
跟前面建立第一級索引的方式相似咐蚯，在第一級索引的基礎(chǔ)之上童漩，每兩個結(jié)點就抽出一個結(jié)點到第二級索引。現(xiàn)在再來查找16春锋，只需要遍歷6個結(jié)點了矫膨，需要遍歷的結(jié)點數(shù)量又減少了。
例子中的數(shù)據(jù)量不大期奔，所以即便 加了兩級索引侧馅，查找效率的提升也并不明顯。為了能真切地感受索引提升查詢效率呐萌。64個結(jié)點的鏈表馁痴，建立了五級索引，如下圖
原來沒有索引的時候肺孤，查找62需要遍歷62個結(jié)點罗晕，現(xiàn)在只需要遍歷11個結(jié)點，速度是不是提高了很多赠堵。所以小渊，當(dāng)鏈表的長度n比較大時，在構(gòu)建索引之后茫叭，查找效率的提升就會非常明顯酬屉。
這種鏈表加多級索引的結(jié)構(gòu)，就是跳表揍愁。
用跳表查詢到底有多快呐萨？
在一個單鏈表中查詢某個數(shù)據(jù)的時間復(fù)雜度是O(n)。那在一個具有多級索引的跳表中吗垮，查詢某個數(shù)據(jù)的時間復(fù)雜度是多少呢垛吗？
如果鏈表里有n個結(jié)點，會有多少級索引呢烁登？
按照剛才所述怯屉，每兩個結(jié)點會抽出一個結(jié)點作為上一級索引的結(jié)點蔚舀，那第一級索引的結(jié)點個數(shù)大約就是n/2，第二級索引的結(jié)點個數(shù)大約就是n/4锨络，第三級索引的結(jié)點個數(shù)大約就是n/8赌躺，依次類推，也就是說羡儿，第k級索引的結(jié)點個數(shù)是第k-1級索引的結(jié)點個數(shù)的1/2礼患，那第k級索引結(jié)點的個數(shù)就是n/(2的k次方)。
假設(shè)索引有h級掠归，最高級的索引有2個結(jié)點缅叠。可以求得h = log2n -1虏冻。如果包含原始鏈表這一層肤粱，整個跳表的高度就是log2n。在跳表中查詢某個數(shù)據(jù)的時候厨相，如果每一層都要遍歷m個結(jié)點领曼，那在跳表中查詢一個數(shù)據(jù)的時間復(fù)雜度就是O(m * logn)。那這個m的值時多少呢蛮穿？按照前面這種索引結(jié)構(gòu)庶骄，每一級索引都最多只需要遍歷3個結(jié)點，也就是說m = 3践磅。
假設(shè)要查找的數(shù)據(jù)是x单刁，在第k級索引中，遍歷到y(tǒng)結(jié)點之后音诈，發(fā)現(xiàn)x大于y幻碱，小于后面的結(jié)點z，所以通過y的down指針细溅，從第k級索引下降到第k-1級索引。在第k-1級索引中儡嘶，y和z之間只有3個結(jié)點（包含y和z）喇聊，所以，在k-1級索引中最多只需要遍歷3個結(jié)點蹦狂，依次類推誓篱，每一級索引都最多只需要遍歷3個結(jié)點。
通過上面的分析凯楔，得到m = 3窜骄，所以在跳表中查詢?nèi)我鈹?shù)據(jù)的時間復(fù)雜度就是O(logn)。這個查找的時間復(fù)雜度跟二分查找是一樣的摆屯。換句話說邻遏，基于單鏈表實現(xiàn)了二分查找。這種查詢效率的提升，前提是建立了很多級索引准验，也就是空間換時間的設(shè)計思路赎线。
跳表是不是很浪費內(nèi)存？
比起單鏈表糊饱，跳表需要存儲多級索引垂寥，肯定要消耗更多的存儲空間。那到底需要消耗多少額外的存儲空間呢另锋？來分心一下跳表的空間的復(fù)雜度滞项。
假設(shè)原始鏈表大小為n，那第一級索引大約有n/2個結(jié)點夭坪，第二級索引大約有n/4個結(jié)點文判，以此類推，每上升一級就減少一半台舱，直到剩下2個結(jié)點律杠。把每層索引的結(jié)點數(shù)寫出來，就是一個等比數(shù)列竞惋。
這幾級索引的結(jié)點總和就是n/2 + n/4 + n/ 8 + ... + 8 + 4 + 2 = n - 2柜去。所以，跳表的空間復(fù)雜度是O(n)拆宛。也就是說嗓奢，如果包含n個結(jié)點的單鏈表構(gòu)造成跳表，需要額外再用接近n個結(jié)點的存儲空間浑厚。那有沒有辦法降低索引占用的內(nèi)存空間呢股耽？
前面都是每兩個結(jié)點抽一個結(jié)點到上級索引，如果每三個結(jié)點或者五個結(jié)點钳幅，抽一個結(jié)點到上一級索引物蝙，是不是就不用那么多索引結(jié)點了呢？每三個結(jié)點抽一個結(jié)點到上級索引的示例圖如下
從圖中可以看出敢艰，第一級索引需要大約n/3個結(jié)點诬乞，第二級索引需要大約n/9個結(jié)點。每往上一級钠导，索引結(jié)點個數(shù)都除以3震嫉。為了方便計算假設(shè)最高一級的索引結(jié)點個數(shù)是1.把每級索引的結(jié)點個數(shù)都寫下來，也是一個等比數(shù)列牡属。
通過等比數(shù)列求和公式票堵，總的索引結(jié)點大約就是n/3 + n/9 + n/27 + ... + 9 + 3 + 1 = n / 2。盡管空間復(fù)雜度還是O(n)逮栅，但比上面的每兩個結(jié)點抽一個結(jié)點到索引的構(gòu)建方法悴势，要減少了一半的索引結(jié)點存儲空間窗宇。
