热门标签
当前位置: article > 正文
算法：二分查找法_二分查找算法
作者：IT小白 | 2024-04-17 02:20:43
赞
踩
二分查找算法
引入
二分查找是一种非常简单易懂的快速查找算法，生活中到处可见。
例子一
我们现在来做一个猜字游戏。我随机写一个 0 到 99 之间的数字，然后你来猜我写的是什么。猜的过程中，你每猜一次，我就会告诉你猜的大了还是小了，直到猜中为止。你来想想，如何快速猜中我写的数字呢？
假设我写的数字是 23，猜数过程如下。（如果猜测范围的数字有偶数个，中间数有两个，就选择较小的那个。）
例子2
假设有1000条订单数据，已经按照订单金额从小到大排序，每个订单金额不同，并且最小单位是元。我们现在想知道支付存在金额等于19元的订单。如果存在，则返回订单数据，如果不存在，则返回null。
最简单的方法是从第一各订单开始，一个一个遍历这100个订单，直到找到金额等于19元的订单为止。但这样查找就比较慢，最快情况下，可能要遍历完这1000条记录才能找到。那用二分查找能不能更快速地解决呢？
我们假设只有 10 个订单，订单金额分别是：8，11，19，23，27，33，45，55，67，98。，每次都与区间的中间数据比对大小，缩小查找区间的范围。如下图，low 和 high 表示待查找区间的下标，mid 表示待查找区间的中间元素下标。
思想与性能分析
算法思想
二分查找针对的是一个有序的数据集合，查找思想有点类型分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到知道要查找的元素，或者区间被缩小为0
性能分析
二分查找是一种非常高效的查找算法，其时间复杂度达到了惊人的O(logn)。分析如下：
- 我们假设数据大小是n，每次查找后数据都会缩小为原来的一半，也就是会除以2.最坏情况下，直到查找区间被缩小为空，才停止。
- 可以看出来，这是一个等比数列。其中 n / 2 k = 1 n/2^k =1 n/2k=1 时，k 的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较，所以，经过了 k 次区间缩小操作，时间复杂度就是O(k)。通过 n / 2 k = 1 n/2^k =1 n/2k=1 ，我们可以求得 k = l o g 2 n k=log_2n k=log2n，所以时间复杂度就是 O(logn)。
O(logn) 这种对数时间复杂度。这是一种极其高效的时间复杂度，有的时候甚至比时间复杂度是常量级 O(1) 的算法还要高效。为什么这么说呢？
- 因为logn是一个非常“恐怖”的数量级，即便n非常非常大，对应的logn也很小。比如n 等于 2 的 32 次方，这个数很大了吧？大约是 42 亿。也就是说，如果我们在42亿个数据中用二分查找一个数据，最多也只需要比较32次
- 用大O标记法表示时间复杂度的时候，会省略掉常数、系数和低阶。对于常量级时间复杂度的算法来说，O(1)有可能表示一个非常大的常量值，比如O(1000)、O(10000)。所以，常量级时间复杂度的算法有可能还没有O(logn)的算法执行效率高
- 反过来，对数对应的就是指数。有一个非常著名的“阿基米德与国王下棋的故事”就足以说明“指数”的恐怖。这也是为什么我们说，指数时间复杂度的算法在大规模数据面前是无效的
实现
二分查找的递归与非递归实现
实际上，简单的二分查找并不难写，二分查找的变体才是真正烧脑的。
最简单的情况就是有序数组中不存在重复元素，写法如下：
bool bsearch(std::vector<int> &vec, int value){ if(vec.empty()){ return false; } int low = 0, high = vec.size() - 1; //当前查找的区间 while (low <= high ){ int mid = low + ((high - low ) >> 1); // 相当于 mid=(low+high)/2 ; if(vec[mid] == value){ //找到了 return true; }else if(vec[mid] < value){ low = mid + 1;// 更新要查找的区间 }else{ high = mid - 1;// 更新要查找的区间 } } return false; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
注意，比较容易出错的三个地方如下：
（1）循环退出条件
- 注意是low <= high，而不是low < high
（2）mid的取值
- 不能写成，mid=(low+high)/2 。
- 因为如果 low 和 high 比较大的话，两者之和就有可能会溢出。
- 改进的方法是将 mid 的计算方式写成 low+(high-low)/2。
- 更进一步，如果要将性能优化到极致的话，我们可以将这里的除以 2 操作转化成位运算 low+((high-low)>>1)。因为相比除法运算来说，计算机处理位运算要快得多。
（3）low 和 high 的更新
- low=mid+1，high=mid-1。注意这里的 +1 和 -1，如果直接写成 low=mid 或者high=mid，就可能会发生死循环。比如，当 high=3，low=3 时，如果 a[3] 不等于value，就会导致一直循环不退出。
实际上，二分查找除了用循环来实现，还可以用递归来实现
bool process(std::vector<int> &vec, int low, int high, int value){ if(low > high){ return false; } int mid = low + ((high - low) >> 1); if(vec[mid] == value){ return true; }else if(vec[mid] < value){ return process(vec, mid + 1, high, value); }else{ return process(vec, low, mid - 1, value); } } bool bsearchInternally(std::vector<int> &vec, int value){ return process(vec, 0, vec.size() - 1, value); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
对数器
#include <algorithm> bool test(std::vector<int> vec, int num){ return std::find(vec.begin(), vec.end(), num) != vec.end(); } std::default_random_engine e; std::vector<int> generateRandom(int maxLen, int minValue, int maxValue){ std::uniform_int_distribution<int> distS(1, maxLen); std::uniform_int_distribution<int> distV(minValue, maxValue); std::vector<int> arr; int size = distS(e); arr.resize(size); for (int i = 0; i < size; ++i) { arr[i] = distV(e); } return arr; } int generateNum(int minValue, int maxValue){ std::uniform_int_distribution<int> distV(minValue, maxValue); return distV(e); } template<typename T> void display(std::vector<T>& vec) { std::cout << "vec: " ; for (auto it: vec) { std::cout << it << ","; } std::cout << "\n"; } int main(){ int testTime = 500000; int maxSize = 10; int minValue = -100; int maxValue = 100; bool succeed = true; bool right, ans1, ans2; for (int i = 0; i < testTime; i++) { auto arr = generateRandom(maxSize,minValue, maxValue); std::sort(arr.begin(), arr.end()); int value = generateNum(minValue, maxValue); right = test(arr, value); ans1 = bsearch(arr, value); ans2 = bsearchInternally(arr, value); if (right !=ans1 || ans1 != ans2) { succeed = false; display(arr); printf("target : %d , right : %d, answer: %d, %d\n", value, right, ans1, ans2); break; } } printf("%s", succeed ? "Nice!" : "Fucking fucked!"); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
除了返回是否存在，还可以返回索引
int process(std::vector<int> &vec, int low, int high, int value){
if(low > high){
return -1;
}
int mid = low + ((high - low) >> 1);
if(vec[mid] == value){
return mid;
}else if(vec[mid] < value){
return process(vec, mid + 1, high, value);
}else{
return process(vec, low, mid - 1, value);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
变体
查找最左==给定值的元素
现在有一个从小到大排序的有序数据集合，这个有序数据集合中存在重复的数据，我们希望能够找到第一个等于给定值的数据。
- 100 个人写二分查找就会有 100 种写法。网上有很多关于变形二分查找的实现方法，有很多写得非常简洁，确很烧脑。
- 对于我们做工程开发的人来说，写出易读懂、没 Bug的代码更重要，没有必要太追求非常完美、简洁的写法
思路：
- 如果low 和high形成了有效的区间，那么开始查找
- 取arr[mid]与value比较
- 如果arr[mid] < value：mid一定不是目标值，而且arr[…mid - 1] <= arr[mid]，所以mid以及左边的数都被淘汰，low = mid + 1
- 如果value < arr[mid]：mid一定不是目标值，而且arr[mid] < arr[mid + 1…] ，所以mid以及其右边的数都被淘汰，hight = mid - 1
- 如果value == arr[mid]，说明这个值可能是目标值：
- 是目标值，由两种情况：
- 这个mid是不是已经到了最左边
- 这个mid还有左边，但是arr[mid - 1] != value
- 不是目标值：
- 此时
arr[mid] = arr[mid - 1] == arr[mid - i]== value - 也就是说目标应该在mid的更左边一些，high = mid - 1
- 此时
- 是目标值，由两种情况：
// 查找最左的==value的元素 int bsearch(std::vector<int> &arr, int value){ int low = 0, high = arr.size() - 1; //当前查找的区间 while(low <= high){ int mid = low + ((high - low) >> 1); //易错点 ()一定要用起来 if(value < arr[mid]){ 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; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
对数器
#include <algorithm> int test(std::vector<int> &vec, int num){ for (int i = 0; i <= (int)vec.size() - 1; ++i) { if(vec[i] == num){ return i; } } return -1; } std::default_random_engine e; std::vector<int> generateRandom(int maxLen, int minValue, int maxValue){ std::uniform_int_distribution<int> distS(1, maxLen); std::uniform_int_distribution<int> distV(minValue, maxValue); std::vector<int> arr; int size = distS(e); arr.resize(size); for (int i = 0; i < size; ++i) { arr[i] = distV(e); } return arr; } int generateNum(int minValue, int maxValue){ std::uniform_int_distribution<int> distV(minValue, maxValue); return distV(e); } template<typename T> void display(std::vector<T>& vec) { std::cout << "vec: " ; for (auto it: vec) { std::cout << it << ","; } std::cout << "\n"; } int main(){ int testTime = 100000; int maxSize = 100; int minValue = -50; int maxValue = 10; bool succeed = true; bool right, ans1; for (int i = 0; i < testTime; i++) { auto arr = generateRandom(maxSize,minValue, maxValue); std::sort(arr.begin(), arr.end()); int value = generateNum(minValue, maxValue); right = test(arr, value); ans1 = bsearch(arr, value); if (right !=ans1 ) { succeed = false; display(arr); printf("target : %d , right : %d, answer: %d\n", value, right, ans1); break; } } printf("%s", succeed ? "Nice!" : "Fucking fucked!"); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
查找最右==给定值的元素
// 查找最右的==value的元素 int bsearch(std::vector<int> &arr, int value){ int N = arr.size(); int low = 0, high = N - 1; //当前查找的区间 while(low <= high){ int mid = low + ((high - low) >> 1); if(value < arr[mid]){ 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; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
对数器
#include <algorithm> int test(std::vector<int> &vec, int num){ for (int i = (int)vec.size() - 1; i >= 0; --i) { if(vec[i] == num){ return i; } } return -1; } std::default_random_engine e; std::vector<int> generateRandom(int maxLen, int minValue, int maxValue){ std::uniform_int_distribution<int> distS(1, maxLen); std::uniform_int_distribution<int> distV(minValue, maxValue); std::vector<int> arr; int size = distS(e); arr.resize(size); for (int i = 0; i < size; ++i) { arr[i] = distV(e); } return arr; } int generateNum(int minValue, int maxValue){ std::uniform_int_distribution<int> distV(minValue, maxValue); return distV(e); } template<typename T> void display(std::vector<T>& vec) { std::cout << "vec: " ; for (auto it: vec) { std::cout << it << ","; } std::cout << "\n"; } int main(){ int testTime = 10000; int maxSize = 100; int minValue = -50; int maxValue = 10; bool succeed = true; bool right, ans1; for (int i = 0; i < testTime; i++) { auto arr = generateRandom(maxSize,minValue, maxValue); std::sort(arr.begin(), arr.end()); int value = generateNum(minValue, maxValue); right = test(arr, value); ans1 = bsearch(arr, value); if (right !=ans1 ) { succeed = false; display(arr); printf("target : %d , right : %d, answer: %d\n", value, right, ans1); break; } } printf("%s", succeed ? "Nice!" : "Fucking fucked!"); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
查找最左>=给定值的元素
在有序数组中，查找第一个大于等于给定值的元素。比如，数组中存储的这样一个序列：3，4，6，7，10。如果查找第一个大于等于 5 的元素，那就是 6。
实现一
思路：
- 如果low 和high形成了有效的区间，那么开始查找
- 取arr[mid]与value比较
- 如果
a
r
r
[
m
i
d
]
<
v
a
l
u
e
arr[mid] < value
arr[mid]<value：
- 因为 a r r [ . . . . . m i d ] < a r r [ m i d ] ， a r r [ m i d ] < v a l u e ， v a l u e < = t a r g e t arr[.....mid] < arr[mid] ，arr[mid] < value，value <= target arr[.....mid]<arr[mid]，arr[mid]<value，value<=target，因此包括mid在内，mid的左边的数都可以淘汰掉了
- low = mid + 1
- 如果
v
a
l
u
e
<
=
a
r
r
[
m
i
d
]
value <= arr[mid]
value<=arr[mid]
- 由于 v a l u e < = t a r g e t value <= target value<=target，所以mid是可能值。
- 那么怎么确保mid是最左边的呢？
- mid左边已经没数—> mid == 0
- mid左边还有数，那么arr[mid - 1]与value比较：
- a r r [ m i d − 1 ] < v a l u e arr[mid - 1] < value arr[mid−1]<value，那么是
- 否则，继续缩小区间， h i g h = m i d − 1 high = mid - 1 high=mid−1
- 如果
a
r
r
[
m
i
d
]
<
v
a
l
u
e
arr[mid] < value
arr[mid]<value：
// 查找最右的==value的元素 int bsearch(std::vector<int> arr, int value) { int N = arr.size(); int low = 0, high = arr.size() - 1; while (low <= high) { 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; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
实现二
int bsearch(std::vector<int> &arr, int value){ int N = arr.size(); int low = 0, high = N - 1; //当前查找的区间 int idx = -1; while(low <= high){// 记录最左的对号 int mid = low + ((high - low) >> 1); if(arr[mid] >= value){ idx = mid; high = mid - 1; }else{ low = mid + 1; } } return idx; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
对数器
#include <algorithm> int test(std::vector<int> &arr, int value){ for (int i = 0; i < arr.size(); ++i) { if(value <= arr[i]){ return i; } } return -1; } std::default_random_engine e; std::vector<int> generateRandom(int maxLen, int minValue, int maxValue){ std::uniform_int_distribution<int> distS(1, maxLen); std::uniform_int_distribution<int> distV(minValue, maxValue); std::vector<int> arr; int size = distS(e); arr.resize(size); for (int i = 0; i < size; ++i) { arr[i] = distV(e); } return arr; } int generateNum(int minValue, int maxValue){ std::uniform_int_distribution<int> distV(minValue, maxValue); return distV(e); } template<typename T> void display(std::vector<T>& vec) { std::cout << "vec: " ; for (auto it: vec) { std::cout << it << ","; } std::cout << "\n"; } int main(){ int testTime = 10000; int maxSize = 100; int minValue = -50; int maxValue = 10; bool succeed = true; bool right, ans1; for (int i = 0; i < testTime; i++) { auto arr = generateRandom(maxSize,minValue, maxValue); std::sort(arr.begin(), arr.end()); int value = generateNum(minValue, maxValue); right = test(arr, value); ans1 = bsearch(arr, value); if (right !=ans1 ) { succeed = false; display(arr); printf("target : %d , right : %d, answer: %d\n", value, right, ans1); break; } } printf("%s", succeed ? "Nice!" : "Fucking fucked!"); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
查找最右<=给定值的元素
查找最后一个小于等于给定值的元素。比如，数组中存储了这样一组数据：3，5，6，8，9，10。最后一个小于等于 7 的元素就是6
int bsearch(std::vector<int> &arr, int value){
int low = 0, high = arr.size() - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (arr[mid] > value) {
high = mid - 1;
} else {
if ((mid == arr.size() - 1) || (arr[mid + 1] > value)) return mid;
else low = mid + 1;
}
}
return -1;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
实现二：
int bsearch(std::vector<int> &arr, int value){
int N = arr.size();
int low = 0, high = N - 1; //当前查找的区间
int index = -1; // 记录最右的对号
while (low <= high) {
int mid = low + ((high - low) >> 1);
if (arr[mid] <= value) {
index = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return index;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
局部最小值
思路
- 先看arr[0] < arr[1]是否成立，如果成立，就直接返回arr[0]
- 在看 arr[N - 2] >= arr[N - 1] 是否成立，如果成立，那么就直接返回arr[N - 1]
- 否则，必然存在 arr[0] >= arr[1]，arr[N - 2] < arr[N]，也就是[1~N-2]之间必然存在一个局部最小
int getLessIndex(std::vector<int> arr, int value) { int N = arr.size(); if(N == 0){ return -1; } if(N == 1 || arr[0] < arr[1] ){ return 0; } if(arr[N - 2] > arr[N - 1]){ return N - 1; } int left = 1, right = N - 2, mid; while (left < right) { mid = (left + right) / 2; if (arr[mid] > arr[mid - 1]) { right = mid - 1; } else if (arr[mid] > arr[mid + 1]) { left = mid + 1; } else { return mid; } } return left; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
为什么能二分
-
二分不一定必须要有序的，不是只有有序才能二分，
-
一种策略，如果有一边肯定有或者有一边肯定没有或者有一边可能有但另一边一定没有，则可以去进行二分操作
对数器
二分查找应用场景的局限性
二分查找的时间复杂度是 O(logn)，查找数据的效率非常高。不过，并不是什么情况下都可以用二分查找，它的应用场景是有很大局限性的。那什么情况下适合用二分查找，什么情况下不适合呢？
（1）首先，二分查找依赖的是顺序表结构，简单的来说是数组
- 那二分查找能否依赖其他数据结构呢？比如链表。答案是不可以，主要原因是二分查找算法需要按照下标随机访问元素。数组按照下标随机访问数据的时间复杂度是 O(1)，而链表随机访问的时间复杂度是 O(n)。所以，如果数据使用链表存储，二分查找的时间复杂就会变得很高。
- 二分查找只能用在数据是通过顺序表来存储的数据结构上。如果你的数据是通过其他数据结构存储的，则无法应用二分查找
（2）其次，二分查找针对的是有序数据
- 二分查找的数据必须是有序的，如果无效，我们需要先排序。排序的时间复杂度最低是 O(nlogn)。所以，如果我们针对的是一组静态的数据，没有频繁的插入、删除，我们可以进行一次排序，多次二分查找。这样排序的成本可被均摊，二分查找的边际成本就会比较低
- 但是，如果我们的数据有频繁的插入和删除操作，要想用二分查找，要么每次插入、删除操作之后保证数据仍然有序，要么在每次二分查找之前都先进行排序。针对这种动态数据集合，无论用哪种方法，维护有序的成本都是很高的
- 所以，二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中。针对动态变化的数据结合，二分查找将不再适用。
（3）再次，数据量太小不适合二分查找
- 如果要处理的数据量很小，完全没有必要用二分查找，顺序遍历就足够了。比如我们在一个大小为10的数组中查找一个元素，不管用二分查找还是顺序遍历，查找速度都差不多。只有数据量比较大的时候，二分查找的优势才会比较明显
- 不过，这里有一个例外。如果数据之间的比较操作非常耗时，不管数据量大小，都推荐使用二分查找。比如，数组中存储的都是长度超过300的字符串，如此长的两个字符串之间比对大小，就会非常耗时。我们需要尽可能的减少比较次数，而比较次数的减少会大大提高性能，这个时候二分查找就比顺序遍历更有优势
（4）最后，数据量太大也不适合二分查找
- 二分查找的底层需要依赖数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间连续，对内存的要求比较苛刻。比如，我们有1GB大小的数据，如果希望用数组来存储，那就需要1GB的连续内存空间
- 注意这里的“连续”二字，也就是说，即便有2GB的内存空间剩余，但是如果这剩余的2GB内存空间都是零散的，没有连续的1GB大小的内存空间，那照样无法申请一个1GB大小的数组。而我们的二分查找是作用在数组这种数据结构之上的，所以太大的数据用数组存储就比较吃力了，也就不能用二分查找了。
实际应用
假设我们有 1000 万个整数数据，每个数据占 8 个字节，如何设计数据结构和算法，快速判断某个整数是否出现在这 1000 万数据中？ 我们希望这个功能不要占用太多的内存空间，最多不要超过 100MB。
我们的内存限制是100MB，每个数据大小是8字节，最简单的方法就是将数据存储在数组中，内存占用差不多是80MB，符合内存的限制。我们可以先对这1000万数据从小到大排序，然后在利用二分查找算法，就可以快速查找相要的数据了。
问题是，散列表、二分树这些动态数据结构也能支持快速查找，能不能用散列表和二叉树解决这个问题呢？
答案是不行的。虽然大部分情况下，用二分查找可以解决的问题，用散列表、二叉树都可以解决。但是，不管是散列表还是二叉树，都会需要比较大的额外的内存空间，如果用散列表或者二叉树来存储这 1000 万的数据，用 100MB 的内存肯定是存不下的。而二分查找底层依赖的是数组，除了数据本身之外，不需要额外存储其他信息，是最省内存空间的存储方式。所以刚好能在限定的内存大小下解决这个问题。
问题模式
通过 IP 地址来查找 IP 归属地的功能，如下：
这个功能并不复杂，它是通过维护一个很大的IP地址库来实现的。地址库中包括IP地址范围和归属地的方式。
当我们想要查询 202.102.133.13 这个 IP 地址的归属地时，我们就在地址库中搜索，发现这个 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] 江苏连云港
- 1
- 2
- 3
- 4
- 5
- 6
现在我的问题是，在庞大的地址库中逐一比对 IP 地址所在的区间，是非常耗时的。假设我们有 12 万条这样的 IP 区间与归属地的对应关系，如何快速定位出一个 IP 地址的归属地呢？
分析
如果IP区间和归属地的对应关系不经常更新，我们可以先预先处理这万条数据，让其按照起始IP从小到达排序。如何来排序呢？我们知道，IP地址可以转换为32位的整数。所以，我们可以将起始地址，按照对应的整形值的大小关系，从小到大进行排序。
然后，这个问题就转换为“在有序数据中，查找最后一个小于等于某个给定值的元素了”
当我们要查询某个IP归属地时，可以可以先通过二分查找，找到最后一个起始IP小于等于这个IP的IP区间，然后，检测这个IP是否在这个IP区间内，如果在，我们就取出对应的归属地显示，如果不在，就返回未找到
小结
二分查找的核心思想理解起来非常简单，有点类似分治思想。即每次都通过跟区间中的中间元素对比，将待查找的区间缩小为一半，直到找到要查找的元素，或者区间被缩小为 0。
二分查找虽然性能比较优秀，但应用场景也比较有限。底层必须依赖数组，并且还要求数据是有序的。对于较小规模的数据查找，我们直接使用顺序遍历就可以了，二分查找的优势并不明显。二分查找更适合处理静态数据，也就是没有频繁的数据插入、删除操作。
凡是能用二分查找解决的，绝大部分我们更倾向于用散列表或者二叉查找树。即便是二分查找在内存使用上更节省，但是毕竟内存紧缺的情况并不多。那二分查找真的没什么用处了吗？
实际上，求“值等于给定值”的二分查找确实不怎么会被用到，二分查找更适合用在“近似”查找问题，在这类问题上，二分查找的优势更加明显。比如上面的这几种变体问题，用其他数据结构，比如散列表、二叉树，就比较难实现了。
变体的二分查找算法写起来非常烧脑，需要重点关注的是：终止条件、区间上下界更新方法、返回值选择
声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签
