【实验一】二分查找

一、题目描述

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的情况。