【C语言】 第二章 分支和循环语句 -2

二分查找

        二分查找是一种经典的查找方法，较于普通遍历搜索的时间复杂度O(n)，要快得多，Olog(n)

时间复杂度简单来讲就是程序执行的速度，其中n的幂越高，时间越复杂，执行速度越慢。

        有一天，小明在图书馆，带着一叠书准备离开。

这时警报器响了，原来有本书忘记登记了，小明慌张地一本一本过安检机。

保安大哥看了都蚌埠住了，“你这搜索太慢了”，只见他把书分成2半，分两次把两叠的书过机，把触发警报的一半书分成两半，然后重复上面的 *** 作，不一会就找到那本书。

小明不禁感到佩服，高兴的回了家去。

等着哪天又被用来举例子

        编程中也常用这种思想，比如在一组数中用二分找一个数字，但是每次查找都得知道目标数在左半还是右半。

查数不像上面的例子，只需把一半书过一下机就能同时扫描所有书，编程没法同时查找所有的数，因此二分查找的数组必须是有序的，通过有序数组的中间值与目标值比较，就能知道目标在左半还是右半。

先声明一个有序数组（后面再讲排序）

int arry[]={1,2,3,4,5,6,7};

定义左指针L 与右指针R ，中间值mid，目标值

int L = 0,R = 6;//R=数组长度-1
int mid, target =2;

3种情况

1. 目标值 target
2. 目标值 target>arry[mid]中间值  说明目标值在右半 找右，令L=mid+1，改变区间
3. 目标值 target==arry[mid]中间值  说明找到了目标值，可以退出循环或返回arry[mid]

这里注释看不清我就把 // 去掉了

#include 
int main()
{
	int arry[] = { 1,2,3,4,5,6,7 };
	int L = 0, R = 6;R=数组长度-1
	int mid, target = 2;
	while (L <= R) {这种写法最终找到时 L是等于R 的，所以不能忽略'='
		mid = (L + R) / 2;
		if (target < arry[mid])		//找左
			R = mid - 1;
		else if (target > arry[mid])//找右
			L = mid + 1;
		else {
			printf("找到%d了 位置是%d",arry[mid],mid);
			break;
		}
	}
    if (L > R) {
		printf("没找到");
	}
	return 0;
}

结果   

猜数字游戏

menu函数： 打印菜单

game函数:    判断是否猜到数字

rand函数：   包含在头文件里，根据种子数生成伪随机数。

可以用rand()%a+b，选取范围，a为多少个数，b则为随机数的起始数（0+b）

srand(unsigner int seed)函数： 根据一个参数改变种子数，在每次rand函数前调用一次来改变种子数。

通过传入时间戳为参数，实现每次生成的随机数都是不同的功能。

（如果传入的是个常数，随机数还是一样）

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 

void menu() {
	printf("1.play\n");
	printf("0.quit\n");
}
void game() {
	int number = rand() % 10 + 1;
	int Guess;
	while (1) {
		printf("请输入一个数： \n");
		scanf("%d", &Guess);
		if (Guess > number)
			printf("大了");
		else if (Guess < number)
			printf("小了");
		else {
			printf("对了");
			break;
		}
	}
}

int main()//主函数，函数入口
{
	srand((unsigned int)time(NULL));
	int input;
	do {
		menu();
		scanf("%d", &input);
		switch (input)
		{
		case 1:
			game();
			return 0;
		case 0:
			break;
		default:
			printf("请重新输入\n");
		}
	}while(input);
}