解题思路:
折半/二分查找,必须采用顺序存储。
在有序的数组中,取中间值作为比较对象,若给定值与中间记录的关键字相等,则查找成功;
若给定值小于中间值记录的关键字,则在中间记录的左半区继续查找;
若给定值大于中间记录的关键字,则在中间记录的右半区查找。
注意事项:
#include<stdio.h>
#include<math.h>
int n,a[100001];/*n,与n个数的数组 */
int m,b;
int main()
{
int i,j;
scanf("%d",&n);//输入n
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
}
scanf("%d",&m);//输入m
//使用循环遍历,如果查找的数小于a数组中最小的数,或者大于最大的数,直接输出。
for(i=1;i<=m;i++){
scanf("%d",&b);//输入查找的数
if(a[1]>b){
printf("%d\n",a[1]);
continue;
}
if(a[n]<b){
printf("%d\n",a[n]);
continue;
}
//二分/折半查找
int low=1,high=n;
/*最低下标记录首位,最高下标记录末位*/
int mid;
while(low<=high){
mid=(low+high)/2; /*折半*/
if(a[mid]>b) { /*如果中间的数大于查找的数 */
high=mid-1; /*最高位下标等于中间下标 -1*/
}else{ /*如果中间的数小于查找的数 */
low=mid+1; /*最低下标等于中间下标+1 */
}
}
if(a[low]==b){
printf("%d\n",a[low]);
continue;
}
if(a[low]-b<b-a[low-1]){
printf("%d\n",a[low]);
continue;
}else{
printf("%d\n",a[low-1]);
continue;
}
}
////for循环结束
}
0.0分
0 人评分
数列 (C++代码)浏览:664 |
C语言程序设计教程(第三版)课后习题10.5 (C语言代码)浏览:1448 |
剪刀石头布 (C语言代码)不知道怎么直接在scanf中用枚举变量浏览:1315 |
A+B for Input-Output Practice (V) (C语言代码)浏览:623 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:619 |
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:660 |
母牛的故事 (C语言代码)浏览:1428 |
DNA (C语言描述,蓝桥杯)浏览:1555 |
1025题解浏览:738 |
罗列完美数 (C语言代码)浏览:491 |