二分查找：如何快速定位IP对应的省份地址？

文章来源于极客时间前google工程师−王争专栏。

通过IP地址查找IP归属地功能：

这个功能是通过维护一个很大的IP地址库来实现。地址库中包含IP地址范围和归属地的对应关系。

当我们查询202.201.133.13这个IP地址归属地时，在地址库中搜索，这个IP落在[202.102.133.0,202.102.133.255]这个地址范围内，就可以显示“山东东营市”给用户了。

问题是：在庞大的地址库中逐一比对IP地址所在的区间是非常耗时的。假设我们有12万条这样的IP区间与归属地的对应关系，如何快速定位出一个IP地址的归属地呢？

主要学习二分查找的变形问题。

“十个二分九个错”，二分查找虽然简单，但是想写出没有Bug的二分查找并不容易。

常见的二分查找变形问题：

变体一：查找第一个值等于给定值的元素

简单二分法适用于有序数据集合中不存在重复的数据，我们在其中查找值等于某个给定值的数据。

如下图所示，如果查找第一个等于8的数据？

上图所示，如果用简单二分法的代码实现，首先拿8与区间的中间值a[4]比较，8比6大，于是在下标5到9之间继续查找，下标5和9的中间位置是下标7，刚好等于8，所以代码就返回了。

针对这种情况，可以稍微改造下简单二分法实现。

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

以上代码实现简洁，比较难理解

比较容易理解的实现如下：

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

a[mid]跟要查找的value的大小关系有三种情况：大于、小于、等于。对于a[mid]>value的情况，只需要更新high=mid-1；对于a[mid]

如果mid=0，数组中的第一个元素，那这个肯定就是我们要找的。如果mid不等于0，a[mid]的前一个元素a[mid-1]不等于value，那么a[mid]也是我们要找的第一个给定值的元素。如果等于value，继续更新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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

参照变体一

变体三：查找第一个大于等于给定值的元素

比如，数组中存储的这样一个序列：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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

查找最后一个小于等于给定值的元素

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

解答开篇

如何快速定位出一个IP地址的归属地？

首先预处理这12万条数据，让其按照起始IP从小到大排序。IP可以转化为32位的整型数。

按照起始IP从小到大排序。问题就转化为在有序数组中，查找最后一个小于等于某个给定值的元素了。

我们先通过二分查找，找到最后一个起始IP小于等于这个IP的IP区间，然后，检查这个IP是否在这个IP区间内，如果在就取对应的归属地显示；如果不在，就返回未查到。

总结

**凡是用二分查找能解决的，绝大部分我们更倾向于用散列表或者二叉查找树。**即便是二分查找在内存使用上更节省，但是内存紧缺的情况并不多。二分查找真的没什么用处了吗？

“值等于给定值”的二分查找确实不怎么会被用到，二分查找更适合用在“近似”查找问题，在这类问题上，二分查找的优势更加明显。比如这篇讲到的几种变体问题，用其他数据结构，比如散列表、二叉树，就比较难实现了。

变体二分法，容易因为细节处理不好产生Bug，这些容易出错的细节有：终止条件、区间上下界更新方法、返回值选择。

思考

循环有序数组，比如4，5，6，1，2，3。如何实现一个“值等于给定值”的二分算法呢？

对应leetcode 33题