数据结构&算法模块总结
1.传统二分查找模板问题
public int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == value) {
return mid;
} else if (a[mid] < value) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
可能出现的三种问题：
-
循环退出条件： 不能写成low < high，否则左右边界缩小在一起时找不到mid
-
mid计算溢出：在mid=(low+high)/2，如果low和high?较?的话，两者之和就有可能会溢出。改进方式： l ow+(high-low)/2，性能更优方式： low+((high-low)>>1)。
-
low和hign更新：low=mid+1，high=mid-1， 不能写成low=mid或high=mid，否则死循环
2.四种二分查找变体
(1)查找第一个值等于给定值的元素
(2)查找最后一个值等于给定值的元素
(3)查找第一个大于等于给定值的元素
(4)查找最后一个小于等于给定值的元素
3.二分查找实现场景
(1)如何在1000万个整数中快速查找某个整数？
?? ?设内存限制是100MB，每个数据??是8字节，最简单的办法就是将数据存储在数组中，内存占?差不多是80MB，符合内存的限制。
?? ?可以先对这1000万数据从?到?排序，然后再利??分查找算法，就可以快速地查找想要的数据了。
? ??
eg.
为什么不用
散列表和二叉树？
?? ?如果?散列表或者?叉树来存储这1000万的数据，
每个节点除了存储数据还要存储邻居或子节点引用关系。?
?分查找底层依赖的是数组，除了数据本身之外，不需要额外存储其他信息，是最省内存空间的存储?式。
(2)如何快速定位IP地址的归属地？
?? ?
问题：
查询202.102.133.13 IP地址的归属地时，在地址库中搜索，发现这个IP地址落在[202.102.133.0, 202.102.133.255]这个地址范围内，其归属地为“山东东营市”。
?? ?
? ? 方法：
如果IP区间与归属地的对应关系不经常更新，我们可以先预处理这12万条数据，让其按照起始IP从?到?排序（IP地址可以转化为32位的整型数）。
? ?
查找过程=“ 在有序数组中，查找最后一个小于等于某个给定值的元素 ”。
??
?
当我们要查询某个IP归属地时，我们可以先通过二分查找，找到最后一个起始IP小于等于这个IP的IP区间，然后，检查这个IP是否在这个IP区间内，如果在，我们就取出对应的归属地显示；如果不在，就返回未查找到。