博客

C语言——折半查找法

折半查找法，顾名思义就是一种查找的方法。优点是其比较次数少，查找速度快，平均性能好。缺点是其

要求的待查表必须是有序表

，且插入删除比较困难。因此，折半查找法适用于不经常变动并且查找次数比较频繁的有序列表。

例如，我买了一件衣服，告诉你在300元以内，让你用次数最少猜出这件衣服的价格？

答：

每次猜中间数


代码展示：用最少次数猜10个数字中有没有7

int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };//要求数组必须是有序的
	int left = 0;//左下标
	int right = sizeof(arr) / sizeof(arr[0]) - 1;//右下标
	int key = 7;//看有没有数字7
	int mid = 0;
	while (left <= right)
	{
		mid = (left + right) / 2;//找到中间的下标
		if (arr[mid] > key)
		{
			right = mid - 1;//如果取的中间的那个数比7还大，说明7在数组的左半部分
		}
		else if (arr[mid] < key)
		{
			left = mid + 1;//如果取的中间的那个数比7还小，说明7在数组的右半部分
		}
		else
			break;//跳出循环,说明这时候arr[mid]==key,找到了
	}
	if (left <= right)
	{
		printf("找到了，下标是：%d\n", mid);
	}
	else
	{
		printf("找不到\n");
	}
}

一个猜数字小游戏的实现


参考代码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void menu()
{
	printf("************************\n");
	printf("****1.play    0.exit****\n");
	printf("************************\n");

}
void game()
{
	int num = 0;//你猜的的数字
	int rand_num = rand() % 100 + 1;//生成一个随机数
	while (1)
	{
		printf("请输入你要猜的数字>:");
		scanf("%d", &num);
		if (num > rand_num)
		{
			printf("猜大了\n");
		}
		else if (num < rand_num)
		{
			printf("猜小了\n");
		}
		else
		{
			printf("恭喜你，猜对了！\n");
			break;
		}
	}
}
int main()
{
	srand((unsigned int)time(NULL));
	int input = 0;//input=1代表玩游戏，input=0代表退出游戏
	do
	{
		menu();//打印一个菜单
		printf("请输入选项>:");
		scanf("%d", &input);
		switch (input)
		{
		case 1:
			game();//玩游戏的函数
			break;
		case 0:
			printf("退出游戏成功！\n");
			break;
		default:
			printf("输入错误有，请重新选择！\n");
			break;
		}
	} while (input);
	return 0;
}

解释一下rand（）函数和srand

rand（）函数是c语言本身就提供的，属于库函数。

而srand是给rand函数初始化的

time（）函数