6-2 sdut-C语言实验-二分查找
分数 20
全屏浏览
切换布局
作者 马新娟
单位 山东理工大学
本题要求实现一个二分查找函数。
给出含有 n 个数的升序序列，保证序列中的数两两不相等，这n个数编号从1 到n。
然后给出 q 次询问，每次询问给出一个数x，若x存在于此序列中，则输出其编号，否则输出-1。
函数接口定义：
int Binary_search(int array[], int l, int r, int x)；
其中 array 、 l 、 r 、 x都是用户传入的参数。 array 是要进行查询的序列，保证序列有序且出现的数字均不重复； l 和 r 是二分查找的区间的左端点和右端点；x 代表要在序列中查询的值。
当在序列中查询到 x 时，函数返回 x 在序列中出现的位置编号；否则函数返回 -1。
裁判测试程序样例：
#include <stdio.h>
int Binary_search(int array[], int l, int r, int x);
int main()
{
int N, Q, i, x, ans;
int array[100005];
scanf("%d",&N); for(i=1; i<=N; i++) { scanf("%d", &array[i]); } scanf("%d",&Q); while(Q--) { scanf("%d", &x); ans = Binary_search(array, 1, N, x); printf("%d\n", ans); } return 0;
}
/* 请在这里填写答案 */
###输入样例：
1. 5 2. 1 3 5 7 9 3. 3 4. 1 5. 5 6. 8
###输出样例：
1. 1 2. 3 3. -1
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
int Binary_search(int array[], int l, int r, int x) { while(l <= r){ int mid = (l + r)/2; if(array[mid] == x) return mid; else if(array[mid] > x) r = mid - 1; else if(array[mid] < x) l = mid + 1; } return -1; //max }
