16 | 二分查詢（下）：如何快速定位IP對應的省份地址？
16 | 二分查詢（下）：如何快速定位IP對應的省份地址？
通過 IP 地址來查詢 IP 歸屬地的功能，不知道你有沒有用過？沒用過也沒關係，你現在可以開啟百度，在搜尋框裡隨便輸一個 IP 地址，就會看到它的歸屬地。
這個功能並不複雜，它是通過維護一個很大的 IP 地址庫來實現的。地址庫中包括 IP 地址範圍和歸屬地的對應關係。
當我們想要查詢202.102.133.13 這個 IP 地址的歸屬地時，我們就在地址庫中搜索，發現這個 IP 地址落在 [202.102.133.0,202.102.133.255] 這個地址範圍內，那我們就可以將這個 IP 地址範圍對應的歸屬地“山東東營市”顯示給使用者了。
[[202.102.133.0](202.102.133.0), [202.102.133.255](202.102.133.255)] 山東東營市 [[202.102.135.0](202.102.135.0), [202.102.136.255](202.102.136.255)] 山東煙臺 [[202.102.156.34](202.102.156.34), [202.102.157.255](202.102.157.255)] 山東青島 [[202.102.48.0](202.102.48.0), [202.102.48.255](202.102.48.255)] 江蘇宿遷 [[202.102.49.15](202.102.49.15), [202.102.51.251](202.102.51.251)] 江蘇泰州 [[202.102.56.0](202.102.56.0), [202.102.56.255](202.102.56.255)] 江蘇連雲港
現在我的問題是，在龐大的地址庫中逐一比對 IP 地址所在的區間，是非常耗時的。假設我們有 12 萬條這樣的 IP 區間與歸屬地的對應關係，如何快速定位出一個 IP 地址的歸屬地呢？
是不是覺得比較難？不要緊，等學完今天的內容，你就會發現這個問題其實很簡單。
上一節我講了二分查詢的原理，並且介紹了最簡單的一種二分查詢的程式碼實現。今天我們來講幾種二分查詢的變形問題。
不知道你有沒有聽過這樣一個說法：“十個二分九個錯”。二分查詢雖然原理極其簡單，但是想要寫出沒有 Bug 的二分查詢並不容易。
唐納德·克努特（Donald E.Knuth）在《計算機程式設計藝術》的第 3 卷《排序和查詢》中說到：“儘管第一個二分查詢演算法於 1946 年出現，然而第一個完全正確的二分查詢演算法實現直到 1962 年才出現。”
你可能會說，我們上一節學的二分查詢的程式碼實現並不難寫啊。那是因為上一節講的只是二分查詢中最簡單的一種情況，在不存在重複元素的有序陣列中，查詢值等於給定值的元素。最簡單的二分查詢寫起來確實不難，但是，二分查詢的變形問題就沒那麼好寫了。
二分查詢的變形問題很多，我只選擇幾個典型的來講解，其他的你可以藉助我今天講的思路自己來分析。
需要特別說明一點，為了簡化講解，今天的內容，我都以資料是從小到大排列為前提，如果你要處理的資料是從大到小排列的，解決思路也是一樣的。同時，我希望你最好先自己動手試著寫一下這 4 個變形問題，然後再看我的講述，這樣你就會對我說的“二分查詢比較難寫”有更加深的體會了。
變體一：查詢第一個值等於給定值的元素
上一節中的二分查詢是最簡單的一種，即有序資料集合中不存在重複的資料，我們在其中查詢值等於某個給定值的資料。如果我們將這個問題稍微修改下，有序資料集合中存在重複的資料，我們希望找到第一個值等於給定值的資料，這樣之前的二分查詢程式碼還能繼續工作嗎？
比如下面這樣一個有序陣列，其中，a[5]，a[6]，a[7] 的值都等於 8，是重複的資料。我們希望查詢第一個等於 8 的資料，也就是下標是 5 的元素。
如果我們用上一節課講的二分查詢的程式碼實現，首先拿 8 與區間的中間值 a[4] 比較，8 比 6 大，於是在下標 5 到 9 之間繼續查詢。下標 5 和 9 的中間位置是下標 7，a[7] 正好等於 8，所以程式碼就返回了。
儘管 a[7] 也等於 8，但它並不是我們想要找的第一個等於 8 的元素，因為第一個值等於 8 的元素是陣列下標為 5 的元素。我們上一節講的二分查詢程式碼就無法處理這種情況了。所以，針對這個變形問題，我們可以稍微改造一下上一節的程式碼。
100 個人寫二分查詢就會有 100 種寫法。網上有很多關於變形二分查詢的實現方法，有很多寫得非常簡潔，比如下面這個寫法。但是，儘管簡潔，理解起來卻非常燒腦，也很容易寫錯。
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (a[mid] >= value) {
high = mid - 1;
} else {
low = mid + 1;
}
}
if (low < n && a[low]==value) return low;
else return -1;
}
看完這個實現之後，你是不是覺得很不好理解？如果你只是死記硬背這個寫法，我敢保證，過不了幾天，你就會全都忘光，再讓你寫，90% 的可能會寫錯。所以，我換了一種實現方法，你看看是不是更容易理解呢？
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid =low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else if (a[mid] < value) {
low = mid + 1;
} else {
if ((mid == 0) || (a[mid - 1] != value)) return mid;
else high = mid - 1;
}
}
return -1;
}
我來稍微解釋一下這段程式碼。a[mid] 跟要查詢的 value 的大小關係有三種情況：大於、小於、等於。對於 a[mid]>value 的情況，我們需要更新 high= mid-1；對於 a[mid]<value 的情況，我們需要更新 low=mid+1。這兩點都很好理解。那當 a[mid]=value 的時候應該如何處理呢？
如果我們查詢的是任意一個值等於給定值的元素，當 a[mid] 等於要查詢的值時，a[mid] 就是我們要找的元素。但是，如果我們求解的是第一個值等於給定值的元素，當 a[mid] 等於要查詢的值時，我們就需要確認一下這個 a[mid] 是不是第一個值等於給定值的元素。
我們重點看第 11 行程式碼。如果 mid 等於 0，那這個元素已經是陣列的第一個元素，那它肯定是我們要找的；如果 mid 不等於 0，但 a[mid] 的前一個元素 a[mid-1] 不等於 value，那也說明 a[mid] 就是我們要找的第一個值等於給定值的元素。
如果經過檢查之後發現 a[mid] 前面的一個元素 a[mid-1] 也等於 value，那說明此時的 a[mid] 肯定不是我們要查詢的第一個值等於給定值的元素。那我們就更新 high=mid-1，因為要找的元素肯定出現在 [low, mid-1] 之間。
對比上面的兩段程式碼，是不是下面那種更好理解？實際上，很多人都覺得變形的二分查詢很難寫，主要原因是太追求第一種那樣完美、簡潔的寫法。而對於我們做工程開發的人來說，程式碼易讀懂、沒 Bug，其實更重要，所以我覺得第二種寫法更好。
變體二：查詢最後一個值等於給定值的元素
前面的問題是查詢第一個值等於給定值的元素，我現在把問題稍微改一下，查詢最後一個值等於給定值的元素，又該如何做呢？
如果你掌握了前面的寫法，那這個問題你應該很輕鬆就能解決。你可以先試著實現一下，然後跟我寫的對比一下。
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid =low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else if (a[mid] < value) {
low = mid + 1;
} else {
if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
else low = mid + 1;
}
}
return -1;
}
我們還是重點看第 11 行程式碼。如果 a[mid] 這個元素已經是陣列中的最後一個元素了，那它肯定是我們要找的；如果 a[mid] 的後一個元素 a[mid+1] 不等於 value，那也說明 a[mid] 就是我們要找的最後一個值等於給定值的元素。
如果我們經過檢查之後，發現 a[mid] 後面的一個元素 a[mid+1] 也等於 value，那說明當前的這個 a[mid] 並不是最後一個值等於給定值的元素。我們就更新 low=mid+1，因為要找的元素肯定出現在 [mid+1, high] 之間。
變體三：查詢第一個大於等於給定值的元素
現在我們再來看另外一類變形問題。在有序陣列中，查詢第一個大於等於給定值的元素。比如，陣列中儲存的這樣一個序列：3，4，6，7，10。如果查詢第一個大於等於 5 的元素，那就是 6。
實際上，實現的思路跟前面的那兩種變形問題的實現思路類似，程式碼寫起來甚至更簡潔。
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid =low + ((high - low) >> 1);
if (a[mid] >= value) {
if ((mid == 0) || (a[mid - 1] < value)) return mid;
else high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
如果 a[mid] 小於要查詢的值 value，那要查詢的值肯定在 [mid+1, high] 之間，所以，我們更新 low=mid+1。
對於 a[mid] 大於等於給定值 value 的情況，我們要先看下這個 a[mid] 是不是我們要找的第一個值大於等於給定值的元素。如果 a[mid] 前面已經沒有元素，或者前面一個元素小於要查詢的值 value，那 a[mid] 就是我們要找的元素。這段邏輯對應的程式碼是第 7 行。
如果 a[mid-1] 也大於等於要查詢的值 value，那說明要查詢的元素在 [low, mid-1] 之間，所以，我們將 high 更新為 mid-1。
變體四：查詢最後一個小於等於給定值的元素
現在，我們來看最後一種二分查詢的變形問題，查詢最後一個小於等於給定值的元素。比如，陣列中儲存了這樣一組資料：3，5，6，8，9，10。最後一個小於等於 7 的元素就是 6。是不是有點類似上面那一種？實際上，實現思路也是一樣的。
有了前面的基礎，你完全可以自己寫出來了，所以我就不詳細分析了。我把程式碼貼出來，你可以寫完之後對比一下。
public int bsearch7(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid =low + ((high - low) >> 1);
if (a[mid] > value) {
high = mid - 1;
} else {
if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
else low = mid + 1;
}
}
return -1;
}
解答開篇
好了，現在我們回頭來看開篇的問題：如何快速定位出一個 IP 地址的歸屬地？
現在這個問題應該很簡單了。如果 IP 區間與歸屬地的對應關係不經常更新，我們可以先預處理這 12 萬條資料，讓其按照起始 IP 從小到大排序。如何來排序呢？我們知道，IP 地址可以轉化為 32 位的整型數。所以，我們可以將起始地址，按照對應的整型值的大小關係，從小到大進行排序。
然後，這個問題就可以轉化為我剛講的第四種變形問題“在有序陣列中，查詢最後一個小於等於某個給定值的元素”了。
當我們要查詢某個 IP 歸屬地時，我們可以先通過二分查詢，找到最後一個起始 IP 小於等於這個 IP 的 IP 區間，然後，檢查這個 IP 是否在這個 IP 區間內，如果在，我們就取出對應的歸屬地顯示；如果不在，就返回未查詢到。
內容小結
上一節我說過，凡是用二分查詢能解決的，絕大部分我們更傾向於用散列表或者二叉查詢樹。即便是二分查詢在記憶體使用上更節省，但是畢竟記憶體如此緊缺的情況並不多。那二分查詢真的沒什麼用處了嗎？
實際上，上一節講的求“值等於給定值”的二分查詢確實不怎麼會被用到，二分查詢更適合用在“近似”查詢問題，在這類問題上，二分查詢的優勢更加明顯。比如今天講的這幾種變體問題，用其他資料結構，比如散列表、二叉樹，就比較難實現了。
變體的二分查詢演算法寫起來非常燒腦，很容易因為細節處理不好而產生 Bug，這些容易出錯的細節有：終止條件、區間上下界更新方法、返回值選擇。所以今天的內容你最好能用自己實現一遍，對鍛鍊編碼能力、邏輯思維、寫出 Bug free 程式碼，會很有幫助。
課後思考
我們今天講的都是非常規的二分查詢問題，今天的思考題也是一個非常規的二分查詢問題。如果有序陣列是一個迴圈有序陣列，比如 4，5，6，1，2，3。針對這種情況，如何實現一個求“值等於給定值”的二分查詢演算法呢？
參考答案
有三種方法查詢迴圈有序陣列
一、
- 找到分界下標，分成兩個有序陣列
- 判斷目標值在哪個有序資料範圍內，做二分查詢
二、
- 找到最大值的下標 x;
- 所有元素下標 +x 偏移，超過陣列範圍值的取模;
- 利用偏移後的下標做二分查詢；
- 如果找到目標下標，再作 -x 偏移，就是目標值實際下標。
兩種情況最高時耗都在查詢分界點上，所以時間複雜度是 O(N）。
複雜度有點高，能否優化呢？
三、
我們發現迴圈陣列存在一個性質：以陣列中間點為分割槽，會將陣列分成一個有序陣列和一個迴圈有序陣列。
如果首元素小於 mid，說明前半部分是有序的，後半部分是迴圈有序陣列；
如果首元素大於 mid，說明後半部分是有序的，前半部分是迴圈有序的陣列；
如果目標元素在有序陣列範圍中，使用二分查詢；
如果目標元素在迴圈有序陣列中，設定陣列邊界後，使用以上方法繼續查詢。
時間複雜度為 O(logN)。
思考題對應leetcode 33題，大家可以去練習