摘要：通過兩個二分查找的條件繼續(xù)進行問題的分析，那么問題又來了，二分查找是快速的查找一個數(shù)據(jù)是否存在一組數(shù)據(jù)中，而且效率極高，億查找一個數(shù)據(jù)只需次查找。二分查找的三點重點循環(huán)退出條件注意是而不是。

這篇文章主要深入數(shù)據(jù)結構與算法在解決實際問題怎么運用和分析的，對于 IP 對屬地查找本身有 API 接口，那這篇文章主要對原理內(nèi)部查詢過程實現(xiàn)做詳細解析，體會怎么將數(shù)據(jù)結構和算法解決實際的問題。

今天主要模擬一下怎么在 20 萬數(shù)據(jù)中定位一個 IP 地址的歸屬地，不知道大家有沒有用過百度搜索過 IP 地址的歸屬地。當我們在百度輸入 IP 地址時，就會出現(xiàn)這個 IP 地址的歸屬地。

或者有一些 IP 歸屬地的查詢工具也可以迅速的查找到 IP 歸屬地。

IP 地址數(shù)據(jù)那么龐大，它是怎么在短短不到一秒時間查找出 IP 地址的歸屬地呢？隨后我?guī)е蓡柲M了在 20 萬條數(shù)據(jù)中快速查找一個 IP 地址的歸屬地。

問題分析

我們知道每個 IP 由兩部分組成的，分別是網(wǎng)絡地址和主機地址。而且每個 IP 地址是隨機動態(tài)分配的，所以說，每個地區(qū)的 IP 地址的前多少位代表哪個地區(qū)，后多少位代表地區(qū)中的局域網(wǎng)。每個所以劃定了 IP 范圍，每個代表不同的歸屬地。

[112.222.133.0, 112.222.133.255]  山東濰坊市
[112.222.135.0, 112.222.136.255]  山東煙臺市 
[112.222.156.34, 112.222.157.255] 山東青島市
[112.222.48.0, 112.222.48.255]  北京朝陽區(qū)
[112.222.49.15, 112.222.51.251] 福建省福州
[112.222.56.0, 112.222.56.255]  廣東省深圳市

我們逐漸的將問題轉化為了數(shù)據(jù)分析問題，也就是說，我們怎么查找一個 IP 地址所屬的范圍從而得出 IP 歸屬地呢？我們可能會想到用快速增刪改查的數(shù)據(jù)結構和算法，平衡樹、散列表、跳表、基于數(shù)組的二分查找等。

IP 地址的區(qū)間是連續(xù)的，可能先考慮到用一下二分查找，但是二分查找是有前提條件的：

1、二分查找是基于順序數(shù)組的，運用的數(shù)組在時間復雜度為 (1) 的時間內(nèi)隨機快速訪問數(shù)據(jù)的特性。

2、二分查找它必須是有序數(shù)據(jù)，而且不能頻繁的進行動態(tài)插入和刪除數(shù)據(jù)，適合一次排序，多次查找的情況回到我們問題符合要求。

通過兩個二分查找的條件繼續(xù)進行問題的分析，那么問題又來了，二分查找是快速的查找一個數(shù)據(jù)是否存在一組數(shù)據(jù)中，而且效率極高，1000億查找一個數(shù)據(jù)只需 36 次查找。但是我們的要解決的問題是在區(qū)間查找。

二分查找的擴展

別著急，二分查找還可能有重復的數(shù)據(jù)，怎么解決？所以二分查找會延伸到查找重復數(shù)據(jù)的第一個數(shù)據(jù)或最后一個數(shù)據(jù)，都可以通過二分查找的算法進行改進的。

如果我們想要查找的 IP 地址在某一區(qū)間內(nèi)，我們能不能轉化為查找最后一個小于等于某一個區(qū)間的起始值。舉個簡單例子：有一下區(qū)間[1,5]、[6,10]、[11,15]、[16、20]，比如 IP 為 9 ，每個區(qū)間的起始值分別為 1、6、11、16，也就是說 9 在這組區(qū)間起始值中，最后一個小于等于 9 的值，也就是 6 ，然后我們拿 9 去區(qū)間[ 6,10] 去查找是否存在該 IP ，如果存在,我們就輸出該區(qū)間對應的 IP 歸屬地。

解決方案

問題已經(jīng)分析完成了，下一步開始將問題轉換為數(shù)據(jù)結構與算法的形式來解決。如果你真認為問題分析完成只剩下寫代碼了，你會接連的遇到棘手的問題。為了能夠讓大家更能體會到實際問題的復雜性，我會采用分步式遞進最終的解決方法。

問題一：當下手開始寫代碼時，你會發(fā)現(xiàn) IP 地址并不是像上述我們用到的整數(shù)，那我們怎么辦呢？

※ 解決：你會想能不能將 IP 轉化為整數(shù)來計算，這里我用 js 來轉化。

1    //將 IP 地址轉化為整數(shù)
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 地址實際上是動態(tài)生成的，怎么來進行模擬那么多隨機的 IP 地址呢？

※ 解決：最大的 IP 是 255.255.255.255 轉化成整數(shù)為 4294967295。也就是 40 億，那我們用隨機函數(shù)在 40 億的范圍內(nèi)隨機生成 20 萬個的 IP 地址。

1    let i = 0;
2    const arrIp = [];
3    //隨機生成 200000 條 IP 數(shù)據(jù)
4    while(i < 10000){
5        const number = Math.floor(Math.random()*10000000);
6        arrIp.push(number);
7        i++;
8    }

問題三：隨機生成的 IP 地址是無序的，我們要進行排序，那么排序的方式有很多，冒泡、歸并、快排、堆排序等，選擇哪一種呢？

※ 解決：對于在 20 萬的 IP 查詢一個 IP 的歸屬地，我用 js 在瀏覽器中實現(xiàn)的，想到存儲空間有限，所以排序空間復雜度不能太高，查詢效率又不能太慢?？炫诺目梢詫崿F(xiàn)空間復雜度為 O(1) 排序，而且排序效率復雜度為 O(nlog2n)

 1    //對 20 萬條數(shù)據(jù)進行快速排序
 2    // 參數(shù)一(arrIP):要排序的數(shù)組IP 參數(shù)二(start):指向起始指針 參數(shù)三(end):指向末尾指針
 3    const quickSort = (arr,startIndex,endIndex) =>{
 4        //遞歸終止條件
 5        if(startIndex < endIndex){
 6            //一般選擇最后一個元素為區(qū)分點(下標索引)
 7            let pivot =  endIndex;
 8            //獲取一組數(shù)據(jù)區(qū)分后的大于 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    // 獲取排好序的區(qū)分點 Index
17    const partition = (arr,pivot,startIndex,endIndex) =>{
18        //獲取到該區(qū)分點的值
19        let pivotVal = arr[pivot];
20        //永遠指向第一個大于 pivot 的值
21        let swapIndex = startIndex;
22        //進行篩選
23        // i 為遍歷數(shù)據(jù)指針
24        for(let i = startIndex; i < endIndex; i++){
25            if(arr[i] < pivotVal){
26                swap(arr,i,swapIndex);
27                swapIndex++;
28            }
29        }
30        //將大于 pivot 的值和小于 pivot 的值中間點和 pivot 的值交換
31        swap(arr,swapIndex,pivot)
32        //返回區(qū)分點的索引
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 在哪一區(qū)間，而不是查找該 IP 地址，所以要對二分查找代碼進行改進，讓其轉化為小于等于某區(qū)間的起始位置。

1   //對 20 萬數(shù)據(jù)匹配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 區(qū)間的終點值[改進]
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 區(qū)間歸屬地我們自己設置幾個簡單的區(qū)間模擬一下，但是實際中很多的 IP 地址歸屬地劃分的很精細的，所以我們在這不多陳述。

代碼我們都做好了，我在這用前端做了一的簡單的交互頁面，我們來模擬一下，你會發(fā)現(xiàn)，當我們劃分區(qū)間后，數(shù)據(jù)并沒有 20 萬，因為我們只記錄區(qū)間的起始值查找就可以了，20 萬數(shù)據(jù)實際大約也就是十幾萬甚至小于這個值。

我們可以設想一下如果把全球的數(shù)據(jù)存儲到瀏覽器中會發(fā)生什么，所以小鹿隨機生成了 50 億的數(shù)據(jù)，來進行排序二分查找，你猜發(fā)生了什么情況？

瀏覽器只在呼呼的轉圈，并不顯示什么，好吧，作為一個前端開發(fā)者，存儲那么多的數(shù)據(jù)來進行操作內(nèi)存溢出了。如果你是一名后臺開發(fā)者，可以嘗試著用后臺語言實現(xiàn)一下，看看能不能數(shù)據(jù)量大時，能不能再進行查找了？

通過上邊的測試，小鹿從中又得出兩個二分查找的適用條件：

1、數(shù)據(jù)量不能太大，數(shù)組在內(nèi)存中需要連續(xù)的內(nèi)存空間，像 java 語言，在內(nèi)存空間緊張的情況下，二分查找就不適用了。但是 js 中的數(shù)組并不是連續(xù)的，而是以哈希映射的方式存在的。

2、數(shù)據(jù)量不能太小，如果數(shù)據(jù)量太小，我們直接遍歷就可以了，無序?qū)憦碗s的二分查找來進行查詢。

二分查找的三點重點：

1、循環(huán)退出條件

注意是 low <= height,而不是 low < heigh。如果是后者，會造成循環(huán)指向一個數(shù)據(jù)。

2、mid 的取值

因為如果 low 比和 height 大的話，兩者之和可能會溢出。應寫成 low+(high-low)/2 ，如果優(yōu)化到極致的話，改進為位運算符 low+((high-low)>>1)。

3、low 和 high 的更新

如果不進行 +1 和 -1 ，就有可能會發(fā)生死循環(huán)。

總結

自從學習數(shù)據(jù)結構與算法以來，發(fā)現(xiàn)它確實能解決很多我們身邊實際的問題，而不僅僅停留到刷各種各樣的算法題上。我們刷算法題的主要目的呢，是提高邏輯思維能力分析能力。還有一種能力也是需要提高的就是一個實際問題怎么才能轉化為數(shù)據(jù)結構和算法問題，再考慮用什么樣的數(shù)據(jù)結構和算法去解決？怎么找到一個最優(yōu)的解決方案？

它對我們的理解、分析、轉化實際問題到數(shù)據(jù)結構與算法提出了一個更高的要求，從之前寫了兩篇用數(shù)據(jù)結構與算法解決實際問題總結來看，我個人覺得不僅僅需要分析問題的能力，還考驗一個人對所有數(shù)據(jù)結構與算法的靈活運用、優(yōu)化、以及思想有很大的挑戰(zhàn)性，因為不局限于一個算法題，還要考慮到實際的很多考慮不到的因素。