大兴网站建设一条龙,企业网站设计开题报告,做网站外包群,wordpress 添加面包屑文章来源于极客时间前google工程师−王争专栏。 通过IP地址查找IP归属地功能#xff1a; 这个功能是通过维护一个很大的IP地址库来实现。地址库中包含IP地址范围和归属地的对应关系。
当我们查询202.201.133.13这个IP地址归属地时#xff0c;在地址库中搜索#xff0c;这个… 文章来源于极客时间前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;
}以上代码实现简洁比较难理解
比较容易理解的实现如下
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;
}a[mid]跟要查找的value的大小关系有三种情况大于、小于、等于。对于a[mid]value的情况只需要更新highmid-1对于a[mid]value的情况只需要更新lowmid1。当a[mid]value的时候该如何处理呢
如果mid0数组中的第一个元素那这个肯定就是我们要找的。如果mid不等于0a[mid]的前一个元素a[mid-1]不等于value那么a[mid]也是我们要找的第一个给定值的元素。如果等于value继续更新highmid-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;
}
参照变体一
变体三查找第一个大于等于给定值的元素
比如数组中存储的这样一个序列346710。如果查找第一个大于等于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;
}
查找最后一个小于等于给定值的元素
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地址的归属地
首先预处理这12万条数据让其按照起始IP从小到大排序。IP可以转化为32位的整型数。
按照起始IP从小到大排序。问题就转化为在有序数组中查找最后一个小于等于某个给定值的元素了。
我们先通过二分查找找到最后一个起始IP小于等于这个IP的IP区间然后检查这个IP是否在这个IP区间内如果在就取对应的归属地显示如果不在就返回未查到。
总结
**凡是用二分查找能解决的绝大部分我们更倾向于用散列表或者二叉查找树。**即便是二分查找在内存使用上更节省但是内存紧缺的情况并不多。二分查找真的没什么用处了吗
“值等于给定值”的二分查找确实不怎么会被用到二分查找更适合用在“近似”查找问题在这类问题上二分查找的优势更加明显。比如这篇讲到的几种变体问题用其他数据结构比如散列表、二叉树就比较难实现了。
变体二分法容易因为细节处理不好产生Bug这些容易出错的细节有终止条件、区间上下界更新方法、返回值选择。
思考
循环有序数组比如456123。如何实现一个“值等于给定值”的二分算法呢
对应leetcode 33题
