二分查找的算法思想
二分查找也称“折半查找”,要求查找表为采用顺序存储结构的有序表。本例一律采用升序排列。二分查找每一次都会比较给定值与序列[low,high]的中间元素,该元素的下标为mid = (low+high)/2,若两者相等,则返回元素的下标为mid;如果arr[mid]>key,说明给定值key在中间元素的左边,此时只需要查找序列[low,mid-1]的中间元素;如果arr[mid]<key,说明给定值key在中间元素的右边,此时只需要查找序列[mid+1,high]。由于每一次比较arr[mid]与key失败都只需要查找剩下序列的一半,故谓之'二分查找'。显而易见,二分查找适合使用递归实现,递归的终止条件为low>high。
代码实现
注意了哈,此处的查找下标从1开始,下标0已经被弃用。
#include<iostream>
using namespace std;
int arr[10] = { 0,1,3,5,12,32,42,53,56,89};
//非递归实现
int Search_Bin(const int key) {
//最左边的下标从1开始
int low = 1, high = 10;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key) {
return mid;
}
else if (arr[mid] < key) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
return -1;
}
//递归实现
int Search_Bin(const int key, int low, int high) {
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] > key)
return Search_Bin(key, low, mid - 1);
else
return Search_Bin(key, mid+1, high);
}
void test01() {
cout << "----调用非递归函数------" << endl;
cout << "ret = 1的下标为" << Search_Bin(1) << endl;
cout << "ret = 43的下标为" << Search_Bin(43) << endl;
cout << "ret = 100的下标为" << Search_Bin(100) << endl;
cout << "----调用递归函数---------" << endl;
int len = sizeof(arr) / sizeof(int);
cout << "ret = 1的下标为" << Search_Bin(1,1,len) << endl;
cout << "ret = 43的下标为" << Search_Bin(43, 1, len) << endl;
cout << "ret = 100的下标为" << Search_Bin(100, 1, len) << endl;
}
int main() {
test01();
return 0;
}
二分查找的判定树
二分查找的过程可以用一棵二叉树来描述,若用二叉树构造序列[low,high]的判定树,那么二叉树的根结点的存储值为序列[low,high]的中间元素的位置mid,而二叉树的左子树构造序列[low,mid-1]的判定树,右子树构造序列[mid+1,high]的判定树。查找给定值key的过程,就是逐一自上而下遍历二叉树根结点的过程。
查找次数不会超过二叉树的深度,假设序列有n个元素,那么查找的次数:count<=[log(2)n]+1。以下构造序列[1,10]的判定树,如图所示,查找的第一个下标必定为5,如果key值较arr[5]小,那么第二个查找的下标必定为2,否则为8。总而言之,倘若查找成功,查找下标的顺序就是二叉树的遍历顺序。
由于判定树的出现只是为了研究二分查找的过程,所以没有代码实现,以下借助判定树分析二分查找的时间复杂度。假设满二叉树的结点为n,j为二叉树的层次,则该层共有2^j-1个结点,由于当查找到第j层的结点时,查找也已与给定值key比较了j次。假设每一个结点被查找到的概率相同,那么每一个结点的平均查找次数为:
可见当n较大时,时间复杂度为log(2)n,相比于顺序查找提升了很多。
优缺点分析
优点:查找速度快;
缺点:
1.只适用于顺序存储结构的有序表;
2.修改与删除操作会破坏查找表的有序性,因而二分查找适合于静态查找表;
反思
二分查找的要求是,查找表为采用顺序存储结构的有序表,但现实中的有序性不只是体现在数字的比较上。有很多的排序标准是人为规定的,比如字典序,ABCD.......Z人为规定为升序排列;一个国家中的各个省市,可以根据经纬度的高低排序,或根据GDP产出排序.......总而言之,倘若一个问题适合采用二分查找,前提是适合指定解决该问题的排序规则,从而方便查找的实现。
另外,现实中的查找并不只是限制于一个值,还可以是一个范围,比如老师查找某个成绩段之间的所有学生,公司根据员工的绩效分段给员工发不同的奖金,学校要求科目成绩在[90,100]分段就可以给出A绩点等等......文章来源:https://www.toymoban.com/news/detail-485646.html
以上就是我对查找学习的一些反思。文章来源地址https://www.toymoban.com/news/detail-485646.html
到了这里,关于二分查找与判定树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!