【实验一】二分查找

【实验一】二分查找

一、题目描述

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

上一篇:队列小哥哥喊你来排队了~(自带循环的那种)


下一篇:数据结构基础03:队列