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

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

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

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

IP 地址數據那么龐大，它是怎么在短短不到一秒時間查找出 IP 地址的歸屬地呢？隨后我帶著疑問模擬了在 20 萬條數據中快速查找一個 IP 地址的歸屬地。

問題分析

我們知道每個 IP 由兩部分組成的，分別是網絡地址和主機地址。而且每個 IP 地址是隨機動態分配的，所以說，每個地區的 IP 地址的前多少位代表哪個地區，后多少位代表地區中的局域網。每個所以劃定了 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]  北京朝陽區
[112.222.49.15, 112.222.51.251] 福建省福州
[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 在瀏覽器中實現的，想到存儲空間有限，所以排序空間復雜度不能太高，查詢效率又不能太慢?？炫诺目梢詫崿F空間復雜度為 O(1) 排序，而且排序效率復雜度為 O(nlog2n)

 1    //對 20 萬條數據進行快速排序
 2    // 參數一(arrIP):要排序的數組IP 參數二(start):指向起始指針 參數三(end):指向末尾指針
 3    const quickSort = (arr,startIndex,endIndex) =>{
 4        //遞歸終止條件
 5        if(startIndex < endIndex){
 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 < 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        //返回區分點的索引
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 < heigh。如果是后者，會造成循環指向一個數據。

2、mid 的取值

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

3、low 和 high 的更新

如果不進行 +1 和 -1 ，就有可能會發生死循環。

總結

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

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