知識星球作者 | 小鹿 來源 | 一個不甘平凡的碼農
這篇文章主要深入資料結構與演演算法在解決實際問題怎麼運用和分析的，對於 IP 對屬地查詢本身有 API 介面，那這篇文章主要對原理內部查詢過程實現做詳細解析，體會怎麼將資料結構和演演算法解決實際的問題。
今天主要模擬一下怎麼在 20 萬資料中定位一個 IP 地址的歸屬地，不知道大家有沒有用過百度搜索過 IP 地址的歸屬地。當我們在百度輸入 IP 地址時，就會出現這個 IP 地址的歸屬地。
或者有一些 IP 歸屬地的查詢工具也可以迅速的查詢到 IP 歸屬地。
IP 地址資料那麼龐大，它是怎麼在短短不到一秒時間查找出 IP 地址的歸屬地呢？隨後我帶著疑問模擬了在 20 萬條資料中快速查詢一個 IP 地址的歸屬地。
問題分析
—————————————
我們知道每個 IP 由兩部分組成的，分別是網路地址和主機地址。而且每個 IP 地址是隨機動態分配的，所以說，每個地區的 IP 地址的前多少位代表哪個地區，後多少位代表地區中的區域網。每個所以劃定了 IP 範圍，每個代表不同的歸屬地。
1[112.222.133.0, 112.222.133.255] 山東濰坊市
2[112.222.135.0, 112.222.136.255] 山東煙臺市
3[112.222.156.34, 112.222.157.255] 山東青島市
4[112.222.48.0, 112.222.48.255] 北京朝陽區
5[112.222.49.15, 112.222.51.251] 福建省福州
6[112.222.56.0, 112.222.56.255] 廣東省深圳市
我們逐漸的將問題轉化為了資料分析問題，也就是說，我們怎麼查詢一個 IP 地址所屬的範圍從而得出 IP 歸屬地呢？我們可能會想到用快速增刪改查的資料結構和演演算法，平衡樹、散串列、跳錶、基於陣列的二分查詢等。
IP 地址的區間是連續的，可能先考慮到用一下二分查詢，但是二分查詢是有前提條件的：
1、二分查詢是基於順序陣列的，運用的陣列在時間複雜度為 (1) 的時間內隨機快速訪問資料的特性。
2、二分查詢它必須是有序資料，而且不能頻繁的進行動態插入和刪除資料，適合一次排序，多次查詢的情況回到我們問題符合要求。
透過兩個二分查詢的條件繼續進行問題的分析，那麼問題又來了，二分查詢是快速的查詢一個資料是否存在一組資料中，而且效率極高，1000億查詢一個資料只需 36 次查詢。但是我們的要解決的問題是在區間查詢。
二分查詢的擴充套件
—————————————
彆著急，二分查詢還可能有重覆的資料，怎麼解決？所以二分查詢會延伸到查詢重覆資料的第一個資料或最後一個資料，都可以透過二分查詢的演演算法進行改進的。
如果我們想要查詢的 IP 地址在某一區間內，我們能不能轉化為查詢最後一個小於等於某一個區間的起始值。舉個簡單例子：有一下區間[1,5]、[6,10]、[11,15]、[16、20]，比如 IP 為 9 ，每個區間的起始值分別為 1、6、11、16，也就是說 9 在這組區間起始值中，最後一個小於等於 9 的值，也就是 6 ，然後我們拿 9 去區間[ 6,10] 去查詢是否存在該 IP ，如果存在,我們就輸出該區間對應的 IP 歸屬地。
解決方案
—————————————
問題已經分析完成了，下一步開始將問題轉換為資料結構與演演算法的形式來解決。如果你真認為問題分析完成只剩下寫程式碼了，你會接連的遇到棘手的問題。為了能夠讓大家更能體會到實際問題的複雜性，我會採用分步式遞進最終的解決方法。
問題一：當下手開始寫程式碼時，你會發現 IP 地址並不是像上述我們用到的整數，那我們怎麼辦呢？
※ 解決：你會想能不能將 IP 轉化為整數來計算，這裡我用 js 來轉化。
1 //將 IP 地址轉化為整數
2 const ipInt = (ip) =>{
3 //IP轉成整型
4 var num = 0;
5 ip = ip.split(".");
6 num = Number(ip[0]) * 256 * 256 * 256 + Number(ip[1]) * 256 * 256 + Number(ip[2]) * 256 + Number(ip[3]);
7 num = num >>> 0;
8 return num;
9 }
問題二：IP 地址實際上是動態生成的，怎麼來進行模擬那麼多隨機的 IP 地址呢？
※ 解決：最大的 IP 是 255.255.255.255 轉化成整數為 4294967295。也就是 40 億，那我們用隨機函式在 40 億的範圍內隨機生成 20 萬個的 IP 地址。
1 let i = 0;
2 const arrIp = [];
3 //隨機生成 200000 條 IP 資料
4 while(i 10000){
5 const number = Math.floor(Math.random()*10000000);
6 arrIp.push(number);
7 i++;
8 }
問題三：隨機生成的 IP 地址是無序的，我們要進行排序，那麼排序的方式有很多，冒泡、歸併、快排、堆排序等，選擇哪一種呢？
※ 解決：對於在 20 萬的 IP 查詢一個 IP 的歸屬地，我用 js 在瀏覽器中實現的，想到儲存空間有限，所以排序空間複雜度不能太高，查詢效率又不能太慢。快排的可以實現空間複雜度為 O(1) 排序，而且排序效率複雜度為 O(nlog2n) 。
1 //對 20 萬條資料進行快速排序
2 // 引數一(arrIP):要排序的陣列IP 引數二(start):指向起始指標 引數三(end):指向末尾指標
3 const quickSort = (arr,startIndex,endIndex) =>{
4 //遞迴終止條件
5 if(startIndex 6 //一般選擇最後一個元素為區分點(下標索引)
7 let pivot = endIndex;
8 //獲取一組資料區分後的大於 pivot 點最後元素的索引
9 let partitionIndex = partition(arr,pivot,startIndex,endIndex);
10 //進行遞迴
11 quickSort(arr,startIndex,partitionIndex-1);
12 quickSort(arr,partitionIndex+1,endIndex);
13 }
14 }
15
16 // 獲取排好序的區分點 Index
17 const partition = (arr,pivot,startIndex,endIndex) =>{
18 //獲取到該區分點的值
19 let pivotVal = arr[pivot];
20 //永遠指向第一個大於 pivot 的值
21 let swapIndex = startIndex;
22 //進行篩選
23 // i 為遍歷資料指標
24 for(let i = startIndex; i 25 if(arr[i] 26 swap(arr,i,swapIndex);
27 swapIndex++;
28 }
29 }
30 //將大於 pivot 的值和小於 pivot 的值中間點和 pivot 的值交換
31 swap(arr,swapIndex,pivot)
32 //傳回區分點的索引
33 return swapIndex;
34 }
35
36 //交換
37 const swap = (arr,i,j) =>{
38 let temp = arr[i];
39 arr[i] = arr[j];
40 arr[j] = temp;
41 }
問題四: 因為我們要做的是查詢某 IP 在哪一區間，而不是查詢該 IP 地址，所以要對二分查詢程式碼進行改進，讓其轉化為小於等於某區間的起始位置。
※ 解決：
1 //對 20 萬資料匹配IP對屬地(二分查詢)
2 const findIpAddress = (arr,value) =>{
3 //宣告兩個指標
4 let low = 0;
5 let high = arr.length - 1;
6
7 while(low <= high){
8 //取中間值
9 let mid = Math.floor((low + (high - low))/2);
10 //判斷中間值
11 if(arr[mid] <= value){
12 //進一步判斷是否是小於 IP 區間的終點值[改進]
13 if(mid == arr.length - 1 || arr[mid + 1] > value){
14 return mid;
15 }else{
16 low = mid + 1;
17 }
18 }else{
19 high = mid - 1;
20 }
21 }
22 return false;
23 }
IP 區間歸屬地我們自己設定幾個簡單的區間模擬一下，但是實際中很多的 IP 地址歸屬地劃分的很精細的，所以我們在這不多陳述。
程式碼我們都做好了，我在這用前端做了一的簡單的互動頁面，我們來模擬一下，你會發現，當我們劃分割槽間後，資料並沒有 20 萬，因為我們只記錄區間的起始值查詢就可以了，20 萬資料實際大約也就是十幾萬甚至小於這個值。
我們可以設想一下如果把全球的資料儲存到瀏覽器中會發生什麼，所以小鹿隨機生成了 50 億的資料，來進行排序二分查詢，你猜發生了什麼情況？
瀏覽器只在呼呼的轉圈，並不顯示什麼，好吧，作為一個前端開發者，儲存那麼多的資料來進行操作記憶體上限溢位了。如果你是一名後臺開發者，可以嘗試著用後臺語言實現一下，看看能不能資料量大時，能不能再進行查找了？
透過上邊的測試，小鹿從中又得出兩個二分查詢的適用條件：
1、資料量不能太大，陣列在記憶體中需要連續的記憶體空間，像 java 語言，在記憶體空間緊張的情況下，二分查詢就不適用了。但是 js 中的陣列並不是連續的，而是以雜湊對映的方式存在的。
2、資料量不能太小，如果資料量太小，我們直接遍歷就可以了，無序寫複雜的二分查詢來進行查詢。
二分查詢的三點重點：
1、迴圈退出條件
註意是 low <= height,而不是 low 如果是後者，會造成迴圈指向一個資料。
2、mid 的取值
因為如果 low 比和 height 大的話，兩者之和可能會上限溢位。應寫成 low+(high-low)/2 ，如果最佳化到極致的話，改進為位運運算元 low+((high-low)>>1)。
3、low 和 high 的更新
如果不進行 +1 和 -1 ，就有可能會發生死迴圈。
總結
—————————————
自從學習資料結構與演演算法以來，發現它確實能解決很多我們身邊實際的問題，而不僅僅停留到刷各種各樣的演演算法題上。我們刷演演算法題的主要目的呢，是提高邏輯思維能力分析能力。還有一種能力也是需要提高的就是一個實際問題怎麼才能轉化為資料結構和演演算法問題，再考慮用什麼樣的資料結構和演演算法去解決？怎麼找到一個最優的解決方案？
它對我們的理解、分析、轉化實際問題到資料結構與演演算法提出了一個更高的要求，從之前寫了兩篇用資料結構與演演算法解決實際問題總結來看，我個人覺得不僅僅需要分析問題的能力，還考驗一個人對所有資料結構與演演算法的靈活運用、最佳化、以及思想有很大的挑戰性，因為不侷限於一個演演算法題，還要考慮到實際的很多考慮不到的因素。
朋友會在“發現-看一看”看到你“在看”的內容