基本思想:
在一个查找区间中,确定出查找区间的中心位置,用待查找数据元素的关键字和中心位置上数据元素的关键字比较,若两者相等则查找成功;否则若前者小于后者,则把区间定为原查找区间的前半段,继续这样的过程;否则若前者大于后者,则把查找的区间定为原查找区间的后半段,继续这样的过程.这样的查找过程一直进行到查找区间的上界小于查找区间的下界为止.由于二分查找算法每次比较后都把查找区间折半,所以该算法也称做折半查找算法.
循环结构的二分查找:
// 在有序表a[0]--a[n-1]中二分查找关键码为key的数据元素,
// 查找成功时返回该元素的下标序号;失败时返回-1
int BiSearch(int a[],int n,int key)
{
int low=0,high=n-1;
int mid;
while (low<=high)
{
mid=(low+high)/2; // 确定查找区间
if(a[mid]==key)return mid; // 查找成功
else if(a[mid]<key)low=mid+1;
else high=mid-1;
}
return -1; // 查找失败
}
递归结构的二分查找:
int BSearch(int a[],int x,int low,int high)
{
int mid;
if(low>high) return -1; // 查找不成功
mid=(low+high)/2;
if(x==a[mid])
return mid; // 查找成功
else if(x<a[mid])
return BSearch(a,x,low,mid-1); // 在下半区查找
else
return BSearch(a,x,mid+1,high); // 在上半区查找
}
分享到:
相关推荐
有序顺序表的二分查找的递归算法.pdf
一、实验目的: 熟悉各种查找算法及其复杂性,能够根据实际情况选择合适的存储结构。 二、实验要求: 1、掌握查找的基本方法。 2、提交实验报告,报告...编程分别对有序顺序表的顺序查找,二分查找算法进行实现。
1.学生基本数据的有序表输入 2....学生基本数据的有序表的二分法查找4.学生基本数据的有序二叉树建立 5.学生基本数据的有序二叉树前序遍历输出 6.学生基本数据的有序二叉树前序遍历输出 7.学生基本数据的有序二叉树查找
基于二分查找的有序表,在做topK算法的给力实现
二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表...
1.二分查找又称为折半查找,它要求要查找的顺序表必须是有序表,即表中结点按关键字有序.并且要用顺序存储结构。 基本思想是:首先将给定值key与表中中间位置记录的关键字相比较,若二者相等,则查找成功,否则...
基于平行数组与二分查找的有序符号表是《算法》中的经典查找算法,本程序使用 Python 语言,实现有序符号表。 ST.py 包含两个类,ST 和 OrderedST。 ST是无序的符号表,基于链表实现。按照顺序将键值对插入链表。 ...
主要介绍了PHP有序表查找之二分查找(折半查找)算法,简单介绍了二分查找法的概念、原理并结合实例形式分析了php基于二分查找算法进行有序线性表查找的相关操作技巧,需要的朋友可以参考下
C 语言中效率最高的查找方式,非常实用。...函数功能: 二分查找 入口参数: 待查找有序表的首地址 int *a 待查找的数据 int num 出口参数: 查找成功返回数据在有序表中的位置0 ~ n-1,不成功返回 -1
顺序和二分查找 课程设计 数组顺序查找 链表顺序查找 C语言编程
使用线性表的间接寻址( class IndirectList )方法,实现二分查找; 查找的数据由键盘输入; 输出线性表和查找的结果(包括次数);
二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好,占用系统内存较少;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素...
9.4对有n个元素的有序表按二分查找方法查找时,最大的查找长度是多少? 9.5设计算法以构造有n个元素(下标范围从1到n)的二分查找的判定树。 9.6判断题:若二叉树中每个结点的值均大于其左孩子的值,小于其右孩子的...
[教学设计]实验十二 实现顺序和二分查找算法.doc
给定一个单调递增的整数序列,问某个整数是否在序列中。输入样例: 5 1 3 4 7 11 3 3 6 9 输出样例: Yes No No
第二行:依次输入n个元素的值(有序) 第三行:输入要查找的关键字key的值 输出格式 输出分两种情形: 1.如果key值存在,则输出其在表中的位置x(表位置从0开始),格式为The element position is x. 2.如果key值...
<1> 对下列数据表,分别采用二分查找算法实现查找,给出查找过程依次所比较的元素(的下标),并以二分查找的判定树来解释。 <2> 设计出在二叉排序树中插入结点的算法,在此基础上实现构建二叉排序树的算法。 <3> ...
(1) 对下列数据表,分别采用二分查找算法实现查找,给出查找过程依次所比较的元素,并以二分查找的判定树来解释。 (2) 设计出在二叉排序树中插入结点的算法,在此基础上实现构建二叉排序树的算法。 (3) 设计算法在...
比较在同一有序表下进行顺序查找和二分查找的效率 表中的奇数从1开始一共n个,要查找searches次。 1.生成新的有序表 2.测试顺序查找的效率" 3.测试binary-search1查找效率 4.测试binary-search2查找效率