上机实验题
题目 【问题描述】给定一个按值有序（升序）的N元整数数组A，采用折半查找法查找关键值k的位置，并给出查找的过程 【输入形式】 第一行：N 第二行：A[0] A[1] … A[N-1] 第三行：k 【输出形式】 第一行：k的位置（索引），若不存在则输出‘no’ 第二行：查找的过程，每一次折半的中间（mid）位置的值，以逗号分隔。例如，1 2 3 4 5的中间位置为3，1 2 3 4的中间位置为2。 【样例输入】 样例1 11 2 5 8 11 15 16 22 24 27 35 50 22 样例2 11 2 5 8 11 15 16 22 24 27 35 50 10 【样例输出】 样例1 6 16 27 22 样例2 no 16 8 11
#include<cstdio> #include<iostream> using namespace std; int main(){ int i; cin>>i; int a[100]; int k; for(k=0;k<i;k++){ cin>>a[k]; } int num; cin>>num; int left =0; int right =i-1; int b[100] ; int b1=0; int index=-1; while(true){ if(a[(left+right)/2]==num){ b[b1++]=num; index=(left+right)/2; break; } if(a[(left+right)/2]<num){ b[b1++]=a[(left+right)/2]; left = (left+right)/2+1; } if(a[(left+right)/2]>num){ b[b1++]=a[(left+right)/2]; right =(left+right)/2-1; } i=right-left; if(i<0){ break; } } if(index != -1){ cout<<index<<endl; }else{ cout<<"no"<<endl; } for(k=0;k<b1;k++){ cout<<b[k]<<" "; } return 0; }