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

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

今天主要模擬一下怎么在 20 萬數(shù)據(jù)中定位一個(gè) IP 地址的歸屬地，不知道大家有沒有用過百度搜索過 IP 地址的歸屬地。當(dāng)我們?cè)诎俣容斎?IP 地址時(shí)，就會(huì)出現(xiàn)這個(gè) IP 地址的歸屬地。

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

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

問題分析

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

[112.222.133.0, 112.222.133.255]  山東濰坊市
[112.222.135.0, 112.222.136.255]  山東煙臺(tái)市 
[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]  廣東省深圳市

我們逐漸的將問題轉(zhuǎn)化為了數(shù)據(jù)分析問題，也就是說，我們?cè)趺床檎乙粋€(gè) IP 地址所屬的范圍從而得出 IP 歸屬地呢？我們可能會(huì)想到用快速增刪改查的數(shù)據(jù)結(jié)構(gòu)和算法，平衡樹、散列表、跳表、基于數(shù)組的二分查找等。

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

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

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

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

二分查找的擴(kuò)展

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

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

解決方案

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

問題一：當(dāng)下手開始寫代碼時(shí)，你會(huì)發(fā)現(xiàn) IP 地址并不是像上述我們用到的整數(shù)，那我們?cè)趺崔k呢？

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

1    //將 IP 地址轉(zhuǎn)化為整數(shù)
2    const ipInt = (ip) =>{
3        //IP轉(zhuǎn)成整型  
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 地址實(shí)際上是動(dòng)態(tài)生成的，怎么來進(jìn)行模擬那么多隨機(jī)的 IP 地址呢？

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

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

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

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

 1    //對(duì) 20 萬條數(shù)據(jù)進(jìn)行快速排序
 2    // 參數(shù)一(arrIP):要排序的數(shù)組IP 參數(shù)二(start):指向起始指針 參數(shù)三(end):指向末尾指針
 3    const quickSort = (arr,startIndex,endIndex) =>{
 4        //遞歸終止條件
 5        if(startIndex < endIndex){
 6            //一般選擇最后一個(gè)元素為區(qū)分點(diǎn)(下標(biāo)索引)
 7            let pivot =  endIndex;
 8            //獲取一組數(shù)據(jù)區(qū)分后的大于 pivot 點(diǎn)最后元素的索引
 9            let partitionIndex = partition(arr,pivot,startIndex,endIndex);
10            //進(jìn)行遞歸
11            quickSort(arr,startIndex,partitionIndex-1);
12            quickSort(arr,partitionIndex+1,endIndex);
13        }
14    }
15
16    // 獲取排好序的區(qū)分點(diǎn) Index
17    const partition = (arr,pivot,startIndex,endIndex) =>{
18        //獲取到該區(qū)分點(diǎn)的值
19        let pivotVal = arr[pivot];
20        //永遠(yuǎn)指向第一個(gè)大于 pivot 的值
21        let swapIndex = startIndex;
22        //進(jìn)行篩選
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 的值中間點(diǎn)和 pivot 的值交換
31        swap(arr,swapIndex,pivot)
32        //返回區(qū)分點(diǎn)的索引
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    }

問題四: 因?yàn)槲覀円龅氖遣樵兡?IP 在哪一區(qū)間，而不是查找該 IP 地址，所以要對(duì)二分查找代碼進(jìn)行改進(jìn)，讓其轉(zhuǎn)化為小于等于某區(qū)間的起始位置。

1   //對(duì) 20 萬數(shù)據(jù)匹配IP對(duì)屬地(二分查找)
 2    const findIpAddress = (arr,value) =>{
 3        //聲明兩個(gè)指針
 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                //進(jìn)一步判斷是否是小于 IP 區(qū)間的終點(diǎn)值[改進(jìn)]
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ū)間歸屬地我們自己設(shè)置幾個(gè)簡單的區(qū)間模擬一下，但是實(shí)際中很多的 IP 地址歸屬地劃分的很精細(xì)的，所以我們?cè)谶@不多陳述。

代碼我們都做好了，我在這用前端做了一的簡單的交互頁面，我們來模擬一下，你會(huì)發(fā)現(xiàn)，當(dāng)我們劃分區(qū)間后，數(shù)據(jù)并沒有 20 萬，因?yàn)槲覀冎挥涗泤^(qū)間的起始值查找就可以了，20 萬數(shù)據(jù)實(shí)際大約也就是十幾萬甚至小于這個(gè)值。

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

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

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

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

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

二分查找的三點(diǎn)重點(diǎn)：

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

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

2、mid 的取值

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

3、low 和 high 的更新

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

總結(jié)

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

它對(duì)我們的理解、分析、轉(zhuǎn)化實(shí)際問題到數(shù)據(jù)結(jié)構(gòu)與算法提出了一個(gè)更高的要求，從之前寫了兩篇用數(shù)據(jù)結(jié)構(gòu)與算法解決實(shí)際問題總結(jié)來看，我個(gè)人覺得不僅僅需要分析問題的能力，還考驗(yàn)一個(gè)人對(duì)所有數(shù)據(jù)結(jié)構(gòu)與算法的靈活運(yùn)用、優(yōu)化、以及思想有很大的挑戰(zhàn)性，因?yàn)椴痪窒抻谝粋€(gè)算法題，還要考慮到實(shí)際的很多考慮不到的因素。