《数据结构》 第八次实验报告 "学生姓名 " " "学生班级 " " "学生学号 " " "指导老师 " " 实验内容 1) 有序表的二分查找 建立有序表，然后进行二分查找 2) 二叉排序树的查找 建立二叉排序树，然后查找 需求分析 二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果 x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x, 如果x>a[n/2],则只要在数组a的右半部搜索x. 时间复杂度无非就是while循环的次数！ 总共有n个元素， 渐渐跟下去就是n,n/2,n/4,....n/2^k（接下来操作元素的剩余个数），其中k就是循 环的次数 由于你n/2^k取整后>=1 即令n/2^k=1 可得k=log2n,（是以2为底，n的对数） 所以时间复杂度可以表示O()=O(logn) 下面提供一段二分查找实现的伪代码: BinarySearch(max,min,des) mid-<(max+min)/2 while(min<=max) mid=(min+max)/2 if mid=des then re
评论0
最新资源