問題：假設我們有 12 萬條這樣的 IP 區(qū)間與歸屬地的對應關系，如何快速定位出一個 IP 地址的歸屬地呢？

二分查找的變形問題：

變體一：查找第一個值等于給定值的元素

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; }

變體二：查找最后一個值等于給定值的元素

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; }

變體三：查找第一個大于等于給定值的元素

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; }

變體四：查找最后一個小于等于給定值的元素

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區(qū)間和歸屬地的對應關系不經常更新，那么我們可以預先處理這12萬的數(shù)，讓其按照ip從小到大進行排序。將ip地址轉化為32位整形數(shù)即可。那么該問題就轉化為找到最后一個小于等于某個給定值的元素類型。

• 查詢某個ip，先通過二分查找找到起始ip小于等于這個ip的ip區(qū)間，然后檢查ip是否在這個ip區(qū)間內，如果在就返回對應的歸屬地顯示；如果不在，就返回未查找到。

總結

以上是生活随笔為你收集整理的16 | 二分查找（下）：如何快速定位IP对应的省份地址？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。