快捷導(dǎo)航

C語言巧用二分查找實現(xiàn)猜數(shù)游戲

更新時間：2022年02月09日 10:41:20 作者：玄澈_

二分查找也稱折半查找（Binary?Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列，本篇文章教你用二分查找編寫猜數(shù)字游戲

（壹）二分查找

?? 1.1 何為二分查找

折半查找，也稱二分查找，在某些情況下相比于順序查找，使用折半查找算法的效率更高。但是該算法的使用的前提是靜態(tài)查找表中的數(shù)據(jù)必須是有序的。

例如，在{5,21,13,19,37,75,56,64,88 ,80,92}這個查找表使用折半查找算法查找數(shù)據(jù)之前，需要首先對該表中的數(shù)據(jù)按照所查的關(guān)鍵字進行排序：{5,13,19,21,37,56,64,75,80,88,92}。

?? 1.2 二分查找的原理

以升序數(shù)列為例，比較一個元素與數(shù)列中的中間位置的元素的大小，如果比中間位置的元素大，則繼續(xù)在后半部分的數(shù)列中進行二分查找；如果比中間位置的元素小，則在數(shù)列的前半部分進行比較；如果相等，則找到了元素的位置。每次比較的數(shù)列長度都會是之前數(shù)列的一半，直到找到相等元素的位置或者最終沒有找到要找的元素。

動圖演示：（于順序查找相比較）

?

?? 1.3 查找條件

二分查找的前提條件是有序數(shù)列，普通查找則不需要。

查找到返回該元素的下標，否則返回-1。

普通查找的時間復(fù)雜度為O(N), 二分查找的時間復(fù)雜度為O(logN)。 N/2/2···/2=1，2^m=N(m為折半查找的次數(shù))，那么m=log(N)，二分查找的時間復(fù)雜度就為O(logN)。

?? 1.4 代碼實現(xiàn)

?? 1.4.1 初始化數(shù)據(jù)

?? 1.4.2 核心函數(shù)

（貳）猜數(shù)字游戲

?? 2.1 菜單初始化

?? 2.2 核心函數(shù)

?? 2.3 main函數(shù)

?? 2.4 總代碼

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
void menu()
{
	printf("**********************************\n");
	printf("*********** 1.play     ***********\n");
	printf("*********** 0.exit     ***********\n");
	printf("**********************************\n");
}
 
//RAND_MAX--rand函數(shù)能返回隨機數(shù)的最大值。
void game()
{
	int random_num = rand() % 100 + 1;
	int input = 0;
	while (1)
	{
		printf("請輸入猜的數(shù)字>:");
		scanf("%d", &input);
		if (input > random_num)
		{
			printf("猜大了\n");
		}
		else if (input < random_num)
		{
			printf("猜小了\n");
		}
		else
		{
			printf("恭喜你，猜對了\n"); break;
		}
	}
}
 
int main()
{
	int input = 0;
	srand((unsigned)time(NULL));
	do
	{
		menu();
		printf("請選擇>:");
		scanf("%d", &input);
		switch (input)
		{
		case 1:
			game();
			break;
		case 0:
			break;
		default:
			printf("選擇錯誤,請重新輸入!\n");
			break;
		}
	} while (input);
	return 0;
}