-
二分(折半)查找算法练习
2020-01-03 15:56:34二分(折半)查找算法练习 Time Limit: 1000 MS Memory Limit: 32768 K Total Submit: 404 (216 ...在一个有序表中利用二分法查找某个关键字是否存在。 Input 输入为多组数据,每组为两行数据,每组中第一行...二分(折半)查找算法练习
Time Limit: 1000 MS Memory Limit: 32768 K
Total Submit: 404 (216 users) Total Accepted: 230 (211 users) Special Judge: No
Description
在一个有序表中利用二分法查找某个关键字是否存在。
Input
输入为多组数据,每组为两行数据,每组中第一行为建立查找的顺序表,第二行是要查找的关键字。
Output
若找到关键字,则输出关键字在表中的位置,否则输出0.
Sample Input
1 2 3 4 510
1 2 3 4 5
5
Sample Output
05
#include<stdio.h> #include<stdlib.h> typedef int elep; #define maxn 1005 struct sq { elep *p; elep length; elep size; }; void insert(sq &l,int x) { l.p[l.length+1]=x;//插入元素 l.length++;//刷新表内元素个数 } sq start() { sq l; l.p=(int *)malloc(maxn*sizeof(elep));//开辟空间 l.length=0; l.size=maxn;//设置最大容量 return l; } int BinarySearch(sq l ,int n, int key){ //折半查找(二分) int low,high,mid; low=1; //最低下标 high=n; //最高下标 while(low<=high){ mid=(low+high)/2; //二分 if(key<l.p[mid]){ high=mid-1; }else if(key>l.p[mid]){ low=mid+1; }else{ return mid; } } return 0; } int main() { sq l; int a,b; l=start(); while(~scanf("%d",&a)) { insert(l,a); if(getchar()=='\n') { scanf("%d",&b); printf("%d\n",BinarySearch(l,l.length,b)); }}}
-
折半查找
2019-04-22 22:52:56折半查找也称二分法查找,是一种在有序数组中查找某一特定元素的搜索算法。这种方法要求待查找的表顺序存储而且必须是有序的。 二、查找过程 首先计算表中间的位置,将表中间位置处的关键字与查找的关键字进行比较...一、定义:
折半查找也称二分法查找,是一种在有序数组中查找某一特定元素的搜索算法。这种方法要求待查找的表顺序存储而且必须是有序的。
二、查找过程
首先计算表中间的位置,将表中间位置处的关键字与查找的关键字进行比较,如果相等,则查找成功;否则利用中间位置将表分为前、后两个子表,如果中间位置的关键字大于查找的关键字,则查找前子表,否则查找后子表。重复上面的过程,直到找到要查找的关键字为止,否则查找失败不存在此关键字。
例:对{2,5,6,9,17,23,54}中的17进行查找
如图,初始时先让low和high在数据集合的头和尾,中间位置为mid,low=0,high=6.所以mid=(0+6)/2=3,即3位置处,关键字为9不等于17,因为17>9//中间位置的关键字小于要查找的关键字,所以应该在后半子表中。接着再计算后半子表中的中间位置:此时low=mid+1,high=high,则mid=(4+6)/2=5,即5处的关键字为23,23不等于17,且17<23//中间位置的关键字大于要查找的关键字,所以应该在前半子表中,前半子表的中间位置为:此时low=low,high=mid-1,则mid=(4+4)/2=4,4处的关键字为17,查找成功结束。以此方法,如果查找的关键字在数据集合中不存在,会出现low>high。所以结束条件为low>high或者找到关键字为止.
a[mid]==key return mid;//中间位置的关键字等于要查找的关键字 a[mid]<key low = mid + 1;//中间位置的关键字小于要查找的关键字 a[mid]>key high = mid - 1;//中间位置的关键字大于要查找的关键字
三、实现
方法一:非递归方法#include<stdio.h> #define N 7 int Search(int a[],int low,int high,int key){ 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 main(void) { int a[N]={2,5,6,9,17,23,54}; int i,key; printf("请输入你要查找的值:"); scanf("%d",&key); i = Search(a,0,N-1,key); printf("%d",i); return 0; }
递归方法
#include<stdio.h> #define N 7 int Search(int a[],int low,int high,int key){ int mid; if(low>high){ return -1; }else{ mid = (low+high)/2; if(a[mid]==key){ return mid; }else if(a[mid]<key){//中间位置的关键字小于要查找的关键字 return Search(a,mid+1,high,key); }else{//中间位置的关键字大于要查找的关键字 return Search(a,low,mid-1,key); } } } int main(void) { int a[N]={2,5,6,9,17,23,54}; int i,key; printf("请输入你要查找的值:"); scanf("%d",&key); i = Search(a,0,N-1,key); printf("%d",i); return 0; }
二分查找会生成一棵二叉查找树
时间复杂度o(lbn) -
编写代码在一个整形有序数组中查找具体的某个数(详细解释)
2020-02-22 01:26:39编写代码在一个整形有序数组中查找具体的某个数 我们如何在一个整形数组中找到某个具体的数呢?今天跟大家分享一个二分查找算法,二分查找又称折半查找。首先,假设表中元素是按升序排列,将表中间位置记录的关键字...编写代码在一个整形有序数组中查找具体的某个数
我们如何在一个整形数组中找到某个具体的数呢?今天跟大家分享一个二分查找算法,二分查找又称折半查找。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
具体代码:int main() { int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };//定义一个整形有序数组 int key = 0;//我们要查找的数 scanf_s("%d", &key); int left = 0;//数组做下标 int right = sizeof(arr) / sizeof(arr[0]) - 1;//数组右下标 while (left <= right)//当满足时,进入循环 { int mid = (left + right) / 2;//求出中间数的下标 if (arr[mid] < key)//key>arr[mid],说明key在中间数右边 { left = mid + 1;//左下标加重新得到一个子表 } else if (arr[mid]>key)//与上面相反 { right = mid - 1; } else { printf("找到了,下标是:%d", mid);//找到的话,打印出下标 break; } } if (left>right)// { printf("没找到"); } return 0; }
运行结果;
二分查找的优点是比较次数少,查找速度快,平均性能好,占用系统内存较少;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。 -
JavaScript使用二分查找算法在数组中查找数据的方法
2021-01-19 16:44:07本文实例讲述了JavaScript使用二分查找算法在数组中查找数据的方法。分享给大家供大家参考。具体分析如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入... -
(C语言实现)静态查找表之有序表的查找
2020-08-02 00:00:13顾名思义,折半查找就是在一个查找范围内以中间点为关键字,与给定值进行比较,从而寻找下一个查找范围。随着查找范围的不断缩小,结果越逼近给定值。 书上的定义:先确定待查记录所在的范围,然后追捕缩小范围知道...我们可以利用有序这个特点,设计一些高效的算法。
例如:1.折半查找 2.斐波那契查找 3.插值查找1.折半查找
实现思路
顾名思义,折半查找就是在一个查找范围内以中间点为关键字,与给定值进行比较,从而寻找下一个查找范围。随着查找范围的不断缩小,结果越逼近给定值。
书上的定义:先确定待查记录所在的范围,然后追捕缩小范围知道找到或者找不到该纪律为止。
代码
int Search_Bin(SSTable ST,int key) { //折半查找。查找num在顺序表ST中的位置 //只适用于有序的顺序表 int i,mid; int low=1; int high=ST.length-1; while(low<=high) { mid=(high+low)/2; if(ST.a[mid]==key) return mid; else if(ST.a[mid]>key) high=mid-1; else low=mid+1; } return 0; }
性能分析
ASL= ((n+1)/n)log2(n+1)-1,当n较大时,ASL=log2(n+1)-1
折半查找的效率比顺序查找的高,但折半查找只适用于有序表,且限于顺序存储结构(对线性链表无法有效地进行折半查找) -
【c练习】二分查找(折半查找)
2020-03-11 14:31:35定义:二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。在C语言顺序存储结构中可更加快捷,时间复杂度更小的查找方式。 算法要求: 1.必须采用顺序存储结构。 2.必须按关键字大小有序排列。 ... -
数据结构之折半查找法——C语言实现
2021-02-05 12:21:07折半查找法又称为二分查找法,该方法要求带查找的表是顺序存储结构并且表中的关键字大小有序排列。 查找过程: 先确定待查记录所在的区间,然后逐渐通过待查找值与区间中间值进行比较进而调整区间大小,不断缩小范围... -
算法_插入排序之折半插入排序
2020-03-26 16:17:51对于递增有序表,我们查找插入位置就是第一个关键字大于插入元素关键字的元素位置,因此折半插入就需要查找有序区中第一个关键字大于要插入元素关键字的元素位置。 综合以上分析 ,可以采用与直接插入排序相同的方法... -
数据结构---耿国华版(课设5)---折半查找
2020-07-08 12:53:461.编写函数,建立有序表,采用折半查找实现某一已知的关键字的查找(采用顺序表存储结构) 2.编写函数,随机产生一组关键字,利用二叉排序树的插入算法建立二叉排序树 3.编写函数,在以上二叉排序树中删除某一指定关键字... -
Python算法 二分查找
2018-12-14 01:03:00二分查找(Binary Search),也被称为折半查找,是在一个有序数组中查找特定元素位置的查找算法。二分查找要求查找序列必须采用顺序存储,且表中元素按关键字有序排列。首先,假设表中元素是按升序排列,将表中间... -
程序员的算法课(4)-二分查找
2019-08-20 22:01:33一个90%的程序员写不对的程序,一个面试高频出现的...但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。 二分查找法充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O... -
数据结构搜索&排序算法题.zip
2020-06-26 11:24:11T1:【折半查找算法】 利用折半查找算法在一个有序表 R 中插入一个关键字 为 k 的元素想,并保持表的有序性。 T2:【二叉排序树算法】 对于二叉排序树 bt,设计一个算法,输出在该树中查找某个关键字 k 所经过的... -
专业课-数据结构(第8章查找作业部分)
2020-11-29 18:47:312.编写一个函数,利用折半查找算法在一个有序表中插入一个元素x,并保持表的有序性。 #include<stdio.h> #define Max 50 //有序表中数据类型 typedef int KeyType; //有序表 typedef struct{ KeyType elem... -
数据结构_C语言_折半插入排序
2020-12-16 16:26:40折半插入排序的基本操作是在一个有序表中进行查找和插入,这个“查找”操作可利用“折半查找”,由此进行的插入排序称之为折半插入排序。 从前面的有序子表中查找出待插入元素应该被插入的位置 给插入位置腾出空间... -
折半插入排序 C语言
2020-11-19 17:10:14①设待排序的记录存放在数组Data[1…n]中,Data[1]是一个有序序列。 ② 循环n-1次,每次使用折半查找法,查找Data[ i ] ( i=2,…,n )在已排好序的序列DataI1…i-1]中的插入位置,然后将Data[ i ]插人表长为i-1的有序... -
【数据结构】折半插入排序
2018-12-31 20:02:38直接插入排序是最简单的排序方法,它采用顺序查找表查找待排序记录在有序序列上的插入位置,而“查找”操作可利用“折半查找”来实现,以“折半查找法”查找插入位置的排序则称为折半插入排序。... -
二分查找
2019-09-25 17:21:32二分查找也叫折半查找,是一种基本的查找算法,这种查找方法需要待查的表满足两个...否则利用中间元素将表一分为二,如果中间关键字大于给定关键字,则在前一子表中进行折半查找,否则在后一子表中进行折半查找。重... -
java数据结构与算法总结(二十九)--关于二分查找和二叉树查找的比较和选择
2021-02-22 23:21:21在一个排序了的整数数组中(包含100万整数),寻找某一个特定的数。二分搜索、先构建二叉树再利用这棵树作为索引进行搜索,这两种搜索的时间复杂度都是logN。 什么时候该用第一种,什么时候该用第二种? 看到这道... -
数据结构与算法之《搜索算法》
2020-06-06 22:24:56搜索算法用于在一个项目集合中查找一个特定的项目。搜索通常的答案是真或假,也可能是找到的某个具体值。常见的搜索算法:顺序查找、二分查找、二叉树查找、哈希查找 1.二分查找 二分查找又称折半查找,优点是比较... -
数据结构与算法Day5 搜索算法
2020-12-03 21:06:32搜索是在一个项目集合中找到一个特定项目的算法过程。搜索的几种常见方法:顺序查找、二分法查找、二叉树查找、哈希查找。 二分法查找 二分查找又称折半查找。 优点 缺点 适用对象 比较次数少,查找速度快,... -
排序算法之插入排序算法
2008-06-15 19:37:00折半插入排序算法基本操作:由于直接插入排序的基本操作是在一个有序表中进行查找的和插入的,所以这个“查找”操作可以利用“折半查找”来实现,这样可以减少查找的时间复杂度。时间复杂度:O(n^2)3. 2-路插入... -
内部排序(3)——插入排序之折半插入排序
2017-05-13 21:26:00因为插入排序的基本思想是在一个有序序列中插入一个新的记录,则能够利用"折半查找"查询插入位置,由此得到的插入排序算法为"折半插入排序"。算法例如以下: void BInsertSort () { // 对顺序表L作折半插入... -
折半插入排序及PHP实现
2018-02-09 13:18:45直接插入排序算法是利用有序表的插入操作来实现对数据集合的排序。在进行第p+1趟的插入排序时,需要在前面的有序序列data[0],data[1],...,data[p]中找到data[p+1]的对应的位置i,同时将data[i],data[i+1],....,data[p... -
排序算法比较
2016-01-02 22:32:001、折半插入排序:插入排序的基本插入是在一个有序表中进行查找和插入,这个查找可利用折半查找来实现,即为折半插入排序。2、起泡排序:首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则将两个... -
搜索--顺序查找、二分查找
2020-08-01 10:46:06搜索是在一个项目集合中找到一个特定项目的算法过程。搜索通常的答案是真的或假的,因为该项目是否存在。 搜索的几种常见方法:顺序查找、二分法查找、二叉树查找、哈希查找 二分法查找 二分查找只能作用于有序的...
-
JMETER 性能测试基础课程
-
深度学习-源码
-
【Python-随到随学】FLask第二周
-
敏捷个人:内容框架之执行力
-
设计模式-适配器模式
-
五金机械工具箱电商淘宝详情页设计模板.zip
-
Docker从入门到精通
-
系统设计:准备系统设计面试问题-源码
-
linux中安装nacos,seata并集成到nacos中
-
Unity ILRuntime框架设计
-
2021 PHP租车系统 毕业设计 毕设源码 源代码使用教程
-
【布道者】Linux极速入门
-
WPF-DataGrid中CheckBox实现全选与非全选
-
50个优秀的名片设计作品欣赏
-
jquery如何判断滚动条是否到底部
-
MySQL 性能优化(思路拓展及实操)
-
SecureCRT 连接 GNS3/Linux 的安全精密工具
-
数据库设计StepbyStep
-
PHP超全局变量
-
Samba 服务配置与管理