java⼆分法模糊匹配_Java算法-⼆分法查
Java 算法 - ⼆分法查
⼆分法查是⼀种⾮常⾼效的查⽅式，时间复杂度为 O(logn)。
唐纳德·克努特(Donald E.Knuth)在《计算机程序设计艺术》的第 3 卷《排序和查》中说到："尽管第⼀个⼆分查算法于 1946 年出现，然⽽第⼀个完全正确的⼆分查算法实现直到 1962 年才出现。"
⼆分查原理⾮常简单，但想要写出没有 Bug 的⼆分查并不容易，"⼗个⼆分九个错"。本⽂先介绍最简单的⼀种⼆分查的代码实现，再深⼊分析⼏种⼆分查的变形问题。
1. ⼯作原理
这⼀部分，我们说的简单⼆分查法，也是精确查。如 JDK 的 Collections#binarySearch。
public int bsearch(int[] arr, int value) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (value < arr[mid]) {
high = mid - 1;
} else if (value == arr[mid]) {
return mid;
} else {
low = mid + 1;
}
}
return -1;
}
说明： 简单的⼆分查⾮常简单，但还是有⼏个细节需要特别注意⼀下： 循环退出条件。注意是 low <= high，⽽不是 low < high，否则可能会查不到数组，反回 -1。 mid 的取值。因为如果 low 和 high ⽐较⼤的话，两者之和就有可能会溢出。写成 low + (high - low) / 2，或改写成位运算 low + ((high - low) >> 1)，或 (low + high) >>> 1。
low 和 high 的更新。如果直接写成 low = mid 或者 high = mid，就可能会发⽣死循环。⽐如，当 high = 3，low = 3 时，如果 a[3] 不等于 value，就会导致⼀直循环不退出。
改进后的⼆分查法如下，以 Collections#binarySearch 为例：
private static int indexedBinarySearch(List extends Comparable super T>> list, T key) {
int low = 0;
int high = list.size() - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
Comparable super T> midVal = (mid);
int cmp = midValpareTo(key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}团体操队形
return -(low + 1); // key not found
}
2. 使⽤场景
⼆分查法虽然查效率⾼效，但使⽤条件⾮常苛刻，场景使⽤有限：
⼆分查的底层数据结构必须是数组。因为需要根据下标随机访问数组。
⼆分查针对的是有序数组。⼆分查只能⽤在插⼊、删除操作不频繁，⼀次排序多次查的场景中。针对动态变化的数据集合，⼆分查将不再适⽤。
对于频繁变化的动态数据，⼆分法不适合。因为每次查前都需要重新排序，虽然查的时间复杂度是 O(logn)，但排序的时间复杂度是
O(nlogn)，因⽽总的时间复杂度就变成 O(nlogn)。
数据量太⼩不适合⼆分查。数据量太⼩则不能体现⼆分查法的优势，还不如直接顺序遍历。
⽐如我们在⼀个⼤⼩为 10 的数组中查⼀个元素，不管⽤⼆分查还是顺序遍历，查速度都差不多。只有数据量⽐较⼤的时候，⼆分查的优势才会⽐较明显。当然，如果数据⽐较操作⾮常耗时，不管数据量⼤⼩，都推荐使⽤⼆分查。如长度超过 300 的字符串⽐较。
数据量太⼤也不适合⼆分查。数据量太⼤内存不够，因为数组必须使⽤连续的内存进⾏存储。⼆分查的底层需要依赖数组这种数据结构，⽽数组为了⽀持随机访问的特性，要求内存空间连续，对内存的要求⽐较苛刻。⽐如，我们有 1GB ⼤⼩的数据，如果希望⽤数组来存储，那就需要 1GB 的连续内存空间。
总结来说：⼆分法查底层必须使⽤有序的静态数组，对于动态数据，或数据量太⼩，或太⼤都不适合⽤⼆分法。
思考1：⼆分查法的底层数据结构为什么不能是链表？
⼆分查法每次都获取链表的中间结点，采⽤快慢结点算法获取链表的中间节点时，快慢指针都要移动链表长度的⼀半次，也就是 n / 2次，总共需要移动 n 次指针才⾏。
第⼀次，链表长度为 n，需要移动指针 n 次；
第⼆次，链表长度为 n / 2，需要移动指针 n / 2 次；
第三次，链表长度为 n / 4，需要移动指针 n / 4 次；
......
以此类推，⼀直到 1 次为值
指针移动的总次数 n + n / 2 + n / 4 + n / 8 + ... + 1 = n(1 - 0.52) / (1 - 0.5) = 2n
也就是说，如果采⽤链表的数据结构，仅获取中间结点的时间复杂度是 O(2n)，不仅远远⼤于数组⼆分查 O(logn)，也要⼤于顺序查的时间复杂度 O(n)。
思考2：动态数据如何快速查呢？
我们知道动态数据每次查前都先进⾏排序后查，查的时间复杂度就变成 O(nlogn)。有没有好的快速查⽅法呢？这时跳表就登场了。跳表使⽤空间换时间的设计思路，通过构建多级索引来提⾼查询的效率，实现了基于链表的“⼆分查”。跳表是⼀种动态数据结构，⽀持快速的插⼊、删除、查操作，时间复杂度都是 O(logn)。
3. 模糊匹配 - ⼆分法查法变形
事实上，⼆分法在精确匹配上使⽤的并不多，我们可以⽤ HashMap 等数据结构替换(虽然 HashMap ⽐数组更耗内存)，⼆分法往往⽤在模糊查上。
查第⼀个值等于给定值的元素
查最后⼀个值等于给定值的元素
查第⼀个⼤于等于给定值的元素
查最后⼀个⼩于等于给定值的元素
3.1 查第⼀个值等于给定值的元素
public int bsearch(int[] arr, int value) {
int n = arr.length;
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (arr[mid] > value) {
high = mid - 1;
} else if (arr[mid] < value) {
low = mid + 1;
} else {
// 和简单⼆分法查不同，如果前⼀个元素值相等还需要继续递归
if ((mid == 0) || (arr[mid - 1] != value)) return mid;
else high = mid - 1;
}
}
return -1;
}
说明： 只需要在⼆分查的基础上做⼀点改动即可，如果查到相等的元素，需要进⼀步判断前⼀个元素是否等于要查的值，如果等于要查的值，则需要继续递归。
上述的⼆分法查代码可读性最好，当然还有⼀种更⾼效的写法，可读性就稍微差⼀点了：
public int bsearch(int[] arr, int value) {
int n = arr.length;
int mid = low + ((high - low) >> 1);
if (arr[mid] >= value) {
high = mid - 1;
} else {
期刊刊次
low = mid + 1;
}
}
if (low < n && arr[low] == value) return low;
else return -1;
}
昂达v972四核版3.2 查最后⼀个值等于给定值的元素
public int bsearch(int[] arr, int value) {
int n = arr.length;
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (arr[mid] > value) {
high = mid - 1;
} else if (arr[mid] < value) {
low = mid + 1;
} else {
if ((mid == n - 1) || (arr[mid + 1] != value)) return mid; else low = mid + 1;
}
}
return -1;
}
3.3 查第⼀个⼤于等于给定值的元素
public int bsearch(int[] arr, int value) {
int n = arr.length;
int mid = low + ((high - low) >> 1);
if (arr[mid] >= value) {
if ((mid == 0) || (arr[mid - 1] < value)) return mid;
else high = mid - 1;
枭之城
} else {
小曾 军营民谣
low = mid + 1;
}
}
return -1;
小哥小}
3.4 查最后⼀个⼩于等于给定值的元素
public int bsearch(int[] arr, int value) {
int n = arr.length;
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (arr[mid] > value) {
high = mid - 1;
} else {
if ((mid == n - 1) || (arr[mid + 1] > value)) return mid;
else low = mid + 1;
}
}
return -1;
}
3.5 模糊匹配应⽤场景
⽐如，我们需要根据 IP 查对应的地址，如果数据库中有 100 万个 IP 段对应的地址库，如何⾼效的进⾏ IP 匹配呢？⽐如：171.43.252.0 ~ 171.43.252.254 武汉
171.43.253.0 ~ 171.43.253.254 ⼴州
171.43.254.0 ~ 171.43.254.254 上海
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议