PTA二分查找 递归
时间: 2023-11-05 18:05:01 浏览: 57
PTA二分查找是一种用于在有序序列中查找指定元素的算法。该算法通过将待查找区间一分为二,然后根据目标元素与中间元素的大小关系确定下一次查找的区间,以此类推,直到找到目标元素或确定目标元素不存在为止。
下面是给出的代码是一个使用二分查找算法查找元素x的示例代码,其中使用了迭代法实现:
#include<stdio.h>
int main(){
int n,x;
int a[1000];
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
scanf("%d",&x);
int left=0,right=n-1,center,sum=0,s=0;
while(left<=right){
sum++;
center=(left+right)/2;
if(x==a[center]){
s++;
printf("%d\n%d\n",center,sum);
}
if(x>a[center]){
left=center+1;
}
else{
right=center-1;
}
}
if(s==0)
printf("-1\n%d\n",sum);
return 0;
}
在这个示例代码中,首先读取输入的n值和n个非降序排列的整数,然后再读取要查找的数x。接下来使用迭代法实现二分查找算法,通过不断更新左右边界的值,直到找到目标元素或确定目标元素不存在为止。最后根据查找结果输出目标元素所在的下标和比较次数。