输入格式:
第一行输入一个整数n,表示有序表的元素个数,接下来一行n个数字,依次为表内元素值。 然后输入一个要查找的值。
输出格式:
输出这个值在表内的位置,如果没有找到,输出”NOT FOUND”。
输入样例:
5
1 3 5 7 9
7
输出样例:
4
输入样例:
5
1 3 5 7 9
10
输出样例:
NOT FOUND
#include <iostream>
using namespace std;
#define MAXSIZE 50
typedef int KeyType;
typedef struct
{ KeyType key;
} ElemType;
typedef struct
{ ElemType *R;
int length;
} SSTable;
void Create(SSTable &T)
{ int i;
T.R=new ElemType[MAXSIZE+1];
cin>>T.length;
for(i=1;i<=T.length;i++)
cin>>T.R[i].key;
}
//
//方法1,
int Search_Bin(SSTable T, KeyType k)
{
int max=T.length;
int min=0;
bool flag=false;
int count=(max-min)/2+1;//指的是mid
while(count)
{
if(T.R[count+min].key==k)
{ flag=true;
break;
}
else if(T.R[count+min].key<k)
{
min=count;
//
//cout<<min+count<<endl;
count/=2;
}
else{
max=count;
//
count=(max-min)/2;
//
}
}
if(flag)
{
return count;
}
else{
return 0;
}
}
//方法2
int Search_Bin(SSTable T, KeyType k)
{
int left=1;
int right=T.length;
int mid=1;
bool flag=false;
while(left<right)
{
mid=(left+right)/2;
if(T.R[mid].key==k)
{
flag=true;
break;
}
if(T.R[mid].key>k)
{
right=mid-1;
}
else{
left=mid+1;
}
}
if(flag)
{
return mid;
}
else{
return 0;
}
}
//
int main ()
{ SSTable T; KeyType k;
Create(T);
cin>>k;
int pos= Search_Bin(T,k);
if(pos==0) cout<<"NOT FOUND"<<endl;
else cout<<pos<<endl;
return 0;
}
//两种方法都能ac,都是二分的思想,推荐用第二种,好想和理解,第一种是自己纯想的,第二种是受一篇文章的启发写的
给一个严格递增数列,函数int Search_Bin(SSTable T, KeyType k)用来二分地查找k在数列中的位置。
函数接口定义:
int Search_Bin(SSTable T, KeyType k)
其中T是有序表,k是查找的值。
裁判测试程序样例:
#include <iostream>
using namespace std;
#define MAXSIZE 50
typedef int KeyType;
typedef struct
{ KeyType key;
} ElemType;
typedef struct
{ ElemType *R;
int length;
} SSTable;
void Create(SSTable &T)
{ int i;
T.R=new ElemType[MAXSIZE+1];
cin>>T.length;
for(i=1;i<=T.length;i++)
cin>>T.R[i].key;
}
int Search_Bin(SSTable T, KeyType k);
int main ()
{ SSTable T; KeyType k;
Create(T);
cin>>k;
int pos=Search_Bin(T,k);
if(pos==0) cout<<"NOT FOUND"<<endl;
else cout<<pos<<endl;
return 0;
}
/* 请在这里填写答案 */
0 分
0 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复