16|二分查找(下):如何快速定位IP对应的省份地址?

[hfuuss]

不知道你有没有听过这样一个说法:“十个二分九个错”。二分查找虽然原理极其简单，但是想要写出没有Bug的二分查找并不容易。

[hfuuss]

上一节我说过，凡是用二分查找能解决的，绝大部分我们更倾向于用散列表或者二叉查找树。即便是二分查找在内存使用上更节省，但是毕竟内存如此紧缺的情况并不多。那二分查找真的没什么用处了吗? 实际上，上一节讲的求“值等于给定值”的二分查找确实不怎么会被用到，二分查找更适合用在“近似”查找问题，在这类问题上，二分查找的优势更加明显。比如今天讲的这几种变体问题，用其他数据结构，比如散列 表、二叉树，就比较难实现了。 变体的二分查找算法写起来非常烧脑，很容易因为细节处理不好而产生Bug，这些容易出错的细节有:终止条件、区间上下界更新方法、返回值选择。所以今天的内容你最好能用自己实现一遍，对锻炼编码能力、逻 辑思维、写出Bug free代码，会很有帮助。

[hfuuss]

[hfuuss]

解答开篇 好了，现在我们回头来看开篇的问题:如何快速定位出一个IP地址的归属地? 现在这个问题应该很简单了。如果IP区间与归属地的对应关系不经常更新，我们可以先预处理这12万条数据，让其按照起始IP从小到大排序。如何来排序呢?我们知道，IP地址可以转化为32位的整型数。所以，我们 可以将起始地址，按照对应的整型值的大小关系，从小到大进行排序。 然后，这个问题就可以转化为我刚讲的第四种变形问题“在有序数组中，查找最后一个小于等于某个给定值的元素”了。 当我们要查询某个IP归属地时，我们可以先通过二分查找，找到最后一个起始IP小于等于这个IP的IP区间，然后，检查这个IP是否在这个IP区间内，如果在，我们就取出对应的归属地显示;如果不在，就返回未查找 到。