16-二分查找（下）：如何快速根据IP定位对应的省份地址？

Posted on | Post modified:
Words count in article: 1.6k | Reading time ≈ 6

开篇问题

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

上一篇我们介绍了有关二分查找的原理，并且实现了一种简单二分查找。今天就来看看几个关于二分查找的变体问题：

binarySearchVariant

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

显然，如果要查找第一个值等于给定值的元素，之前简单进行比较得出元素的方法便不再适用了。现在我们需要判断给定值在数组中是否有重复。

下面我们来看看代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 二分查找：查找第一个值等于给定值的元素
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
17
18
19
20
// 二分查找：查找最后一个值等于给定值的元素
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
18
// 二分查找：查找第一个大于等于给定值的元素
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
16
17
18
//二分查找：查找最后一个小于等于给定值的元素
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((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。针对这种情况，如何实现一个求“值等于给定值”的二分查找算法呢？

@Smallfly
有三种方法查找循环有序数组
一、
1、找到分界下标，分成两个有序数组
2、 判断目标值在哪个有序数据范围内，做二分查找
二、
1、找到最大值的下标 x;
2、所有元素下标 +x 偏移，超过数组范围值的取模;
3、利用偏移后的下标做二分查找；
4、如果找到目标下标，再作 -x 偏移，就是目标值实际下标。
两种情况最高时耗都在查找分界点上，所以时间复杂度是 O(N）。
复杂度有点高，能否优化呢？
三、
我们发现循环数组存在一个性质：以数组中间点为分区，会将数组分成一个有序数组和一
个循环有序数组。
如果首元素小于 mid，说明前半部分是有序的，后半部分是循环有序数组；
如果首元素大于 mid，说明后半部分是有序的，前半部分是循环有序的数组；
如果目标元素在有序数组范围中，使用二分查找；
如果目标元素在循环有序数组中，设定数组边界后，使用以上方法继续查找。
时间复杂度为 O(logN)。

有问题？发送 issues 给我~

0%