关于校园网站建设的通知,wordpress模板和下载不同,网站怎么做七牛云加速,类似传奇的网页游戏二分查找的算法思想二分查找也称“折半查找”#xff0c;要求查找表为采用顺序存储结构的有序表。本例一律采用升序排列。二分查找每一次都会比较给定值与序列[low,high]的中间元素#xff0c;该元素的下标为mid (lowhigh)/2,若两者相等#xff0c;则返回元素的下标为mid;如…二分查找的算法思想二分查找也称“折半查找”要求查找表为采用顺序存储结构的有序表。本例一律采用升序排列。二分查找每一次都会比较给定值与序列[low,high]的中间元素该元素的下标为mid (lowhigh)/2,若两者相等则返回元素的下标为mid;如果arr[mid]key,说明给定值key在中间元素的左边此时只需要查找序列[low,mid-1]的中间元素如果arr[mid]key,说明给定值key在中间元素的右边此时只需要查找序列[mid1,high]。由于每一次比较arr[mid]与key失败都只需要查找剩下序列的一半故谓之二分查找。显而易见二分查找适合使用递归实现递归的终止条件为lowhigh。代码实现注意了哈此处的查找下标从1开始下标0已经被弃用。#includeiostream
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, mid1, 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]的判定树右子树构造序列[mid1,high]的判定树。查找给定值key的过程就是逐一自上而下遍历二叉树根结点的过程。查找次数不会超过二叉树的深度假设序列有n个元素那么查找的次数count[log(2)n]1。以下构造序列[1,10]的判定树如图所示查找的第一个下标必定为5如果key值较arr[5]小那么第二个查找的下标必定为2否则为8。总而言之倘若查找成功查找下标的顺序就是二叉树的遍历顺序。由于判定树的出现只是为了研究二分查找的过程所以没有代码实现以下借助判定树分析二分查找的时间复杂度。假设满二叉树的结点为nj为二叉树的层次则该层共有2^j-1个结点由于当查找到第j层的结点时查找也已与给定值key比较了j次。假设每一个结点被查找到的概率相同那么每一个结点的平均查找次数为可见当n较大时时间复杂度为log(2)n,相比于顺序查找提升了很多。优缺点分析优点查找速度快缺点1.只适用于顺序存储结构的有序表 2.修改与删除操作会破坏查找表的有序性因而二分查找适合于静态查找表反思二分查找的要求是查找表为采用顺序存储结构的有序表但现实中的有序性不只是体现在数字的比较上。有很多的排序标准是人为规定的比如字典序ABCD.......Z人为规定为升序排列一个国家中的各个省市可以根据经纬度的高低排序或根据GDP产出排序.......总而言之倘若一个问题适合采用二分查找前提是适合指定解决该问题的排序规则从而方便查找的实现。另外现实中的查找并不只是限制于一个值还可以是一个范围比如老师查找某个成绩段之间的所有学生公司根据员工的绩效分段给员工发不同的奖金学校要求科目成绩在[90,100]分段就可以给出A绩点等等......以上就是我对查找学习的一些反思。
