【实验一】二分查找
一、题目描述
1001.二分查找
时限:1000ms 内存限制:10000K 总时限:3000ms
描述
给定一个单调递增的整数序列,问某个整数是否在序列中。
输入
第一行为一个整数n,表示序列中整数的个数;第二行为n(n不超过10000)个整数;第三行为一个整数m(m不超过50000),表示查询的个数;接下来m行每行一个整数k。
输出
每个查询的输出占一行,如果k在序列中,输出Yes,否则输出No。
输入样例
5
1 3 4 7 11
3
3
6
9
输出样例
Yes
No
No
二、解题思路及代码实现
1.解题原理
首先用key元素与中间元素进行比较
a.如果key < 中间元素,就只在中间元素前面的区间进行查找,rear = mid - 1;
b.如果key > 中间元素,就只在中间元素后面的区间进行查找,front = mid + 1;
c.如果key = 中间元素,就返回ture;
如果没有找到key元素,就返回false。
2.代码实现
# include <stdio.h>
bool binarysort(int a[], int key, int n);
bool binarysort(int a[], int key, int n)
{
int front = 0, rear = n-1, mid;
while (front <= rear)
{
mid = (front + rear) / 2;
if (key < a[mid])
{
rear = mid - 1;
}
else if (key > a[mid])
{
front = mid + 1;
}
else
{
return true;
}
/*
else
{
return false; //不可以把这个写进while循环里,因为如果当数组里没有key元素时,而且front>rear,就不会进入while循环。
}
*/
}
return false;
}
int main(void)
{
int n, a[10000], testnum, key, i;
scanf ("%d", &n);
for (i = 0; i <= n-1; i++)
{
scanf ("%d", &a[i]);
}
scanf ("%d", &testnum);
while(testnum)
{
scanf ("%d", &key);
if (binarysort(a, key, n))
{
printf("Yes\n");
}
else
{
printf("No\n");
}
testnum--;
}
return 0;
}
总结
1.注意二分查找时最后出现false的情况。