16二分查找(下):如何快速定位IP对应的省份地址?.pdf
《16二分查找(下):如何快速定位IP对应的省份地址?.pdf》由会员分享,可在线阅读,更多相关《16二分查找(下):如何快速定位IP对应的省份地址?.pdf(12页珍藏版)》请在三一文库上搜索。
1、16|二分查找(下):如何快速定位IP对应的省份地址? file:/F/temp/geektime/数据结构与算法之美/16二分查找(下):如何快速定位IP对应的省份地址?.html2019/1/15 15:35:37 16|二分查找(下):如何快速定位IP对应的省份地址? 通过IP地址来查找IP归属地的功能,不知道你有没有用过?没用过也没关系,你现在可以打开百度,在搜索框里随便输一个IP地址,就会看到它的归属地。 这个功能并不复杂,它是通过维护一个很大的IP地址库来实现的。地址库中包括IP地址范围和归属地的对应关系。 当我们想要查询202.102.133.13这个IP地址的归属地时,我们就在
2、地址库中搜索,发现这个IP地址落在202.102.133.0, 202.102.133.255这个地址范围内,那我们就可以将这个IP地址范围对应的归属地“山东东营市”显示给 用户了。 202.102.133.0, 202.102.133.255 山东东营市 202.102.135.0, 202.102.136.255 山东烟台 202.102.156.34, 202.102.157.255 山东青岛 202.102.48.0, 202.102.48.255 江苏宿迁 202.102.49.15, 202.102.51.251 江苏泰州 202.102.56.0, 202.102.56.255
3、江苏连云港 现在我的问题是,在庞大的地址库中逐一比对IP地址所在的区间,是非常耗时的。假设我们有12万条这样的IP区间与归属地的对应关系,如何快速定位出一个IP地址的归属地呢? 是不是觉得比较难?不要紧,等学完今天的内容,你就会发现这个问题其实很简单。 16|二分查找(下):如何快速定位IP对应的省份地址? file:/F/temp/geektime/数据结构与算法之美/16二分查找(下):如何快速定位IP对应的省份地址?.html2019/1/15 15:35:37 上一节我讲了二分查找的原理,并且介绍了最简单的一种二分查找的代码实现。今天我们来讲几种二分查找的变形问题。 不知道你有没有听过
4、这样一个说法:“十个二分九个错”。二分查找虽然原理极其简单,但是想要写出没有Bug的二分查找并不容易。 唐纳德克努特(Donald E.Knuth)在计算机程序设计艺术的第3卷排序和查找中说到:“尽管第一个二分查找算法于1946年出现,然而第一个完全正确的二分查找算法实现直到1962年才出现。” 你可能会说,我们上一节学的二分查找的代码实现并不难写啊。那是因为上一节讲的只是二分查找中最简单的一种情况,在不存在重复元素的有序数组中,查找值等于给定值的元素。最简单的二分查找写起来确实不 难,但是,二分查找的变形问题就没那么好写了。 二分查找的变形问题很多,我只选择几个典型的来讲解,其他的你可以借助
5、我今天讲的思路自己来分析。 需要特别说明一点,为了简化讲解,今天的内容,我都以数据是从小到大排列为前提,如果你要处理的数据是从大到小排列的,解决思路也是一样的。同时,我希望你最好先自己动手试着写一下这4个变形问题,然后 再看我的讲述,这样你就会对我说的“二分查找比较难写”有更加深的体会了。 变体一:查找第一个值等于给定值的元素 16|二分查找(下):如何快速定位IP对应的省份地址? file:/F/temp/geektime/数据结构与算法之美/16二分查找(下):如何快速定位IP对应的省份地址?.html2019/1/15 15:35:37 上一节中的二分查找是最简单的一种,即有序数据集合中
6、不存在重复的数据,我们在其中查找值等于某个给定值的数据。如果我们将这个问题稍微修改下,有序数据集合中存在重复的数据,我们希望找到第一个值等 于给定值的数据,这样之前的二分查找代码还能继续工作吗? 比如下面这样一个有序数组,其中,a5,a6,a7的值都等于8,是重复的数据。我们希望查找第一个等于8的数据,也就是下标是5的元素。 如果我们用上一节课讲的二分查找的代码实现,首先拿8与区间的中间值a4比较,8比6大,于是在下标5到9之间继续查找。下标5和9的中间位置是下标7,a7正好等于8,所以代码就返回了。 尽管a7也等于8,但它并不是我们想要找的第一个等于8的元素,因为第一个值等于8的元素是数组下
7、标为5的元素。我们上一节讲的二分查找代码就无法处理这种情况了。所以,针对这个变形问题,我们可以稍微改 造一下上一节的代码。 100个人写二分查找就会有100种写法。网上有很多关于变形二分查找的实现方法,有很多写得非常简洁,比如下面这个写法。但是,尽管简洁,理解起来却非常烧脑,也很容易写错。 public int bsearch(int a, int n, int value) int low = 0; int high = n - 1; while (low 1); if (amid = value) high = mid - 1; else low = mid + 1; if (low 1)
8、; if (amid value) high = mid - 1; else if (amid value的情况,我们需要更新high= mid-1;对于amid 1); if (amid value) high = mid - 1; else if (amid 1); if (amid = value) if (mid = 0) | (amid - 1 1); if (amid value) high = mid - 1; else if (mid = n - 1) | (amid + 1 value) return mid; else low = mid + 1; return -1; 解
9、答开篇 好了,现在我们回头来看开篇的问题:如何快速定位出一个IP地址的归属地? 现在这个问题应该很简单了。如果IP区间与归属地的对应关系不经常更新,我们可以先预处理这12万条数据,让其按照起始IP从小到大排序。如何来排序呢?我们知道,IP地址可以转化为32位的整型数。所以,我们 可以将起始地址,按照对应的整型值的大小关系,从小到大进行排序。 然后,这个问题就可以转化为我刚讲的第四种变形问题“在有序数组中,查找最后一个小于等于某个给定值的元素”了。 当我们要查询某个IP归属地时,我们可以先通过二分查找,找到最后一个起始IP小于等于这个IP的IP区间,然后,检查这个IP是否在这个IP区间内,如果在
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 16 二分 查找 如何 快速 定位 IP 对应 省份 地址
链接地址:https://www.31doc.com/p-5529978.html