快捷導(dǎo)航

C語(yǔ)言通過(guò)二分查找實(shí)現(xiàn)猜數(shù)字游戲

更新時(shí)間：2023年02月03日 15:18:00 作者：辭七七

這篇文章主要為大家詳細(xì)介紹了在C語(yǔ)言中如何通過(guò)二分查找思想編寫(xiě)一個(gè)簡(jiǎn)單的猜數(shù)字游戲，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下

二分查找

題目：在一個(gè)有序數(shù)組中查找具體的某個(gè)數(shù)字n。

首先我們先定義一個(gè)1···10的數(shù)組，如果7為我們要查找的數(shù)字，編寫(xiě)代碼如下

#include <stdio.h>
int main()
{
    int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
    //  下標(biāo)          0 1 2 3 4 5 6 7 8 9
    int k = 7;//k是要查找的數(shù)字
    int i = 0;
    int sz = sizeof(arr) / sizeof(arr[0]);
     //sz為數(shù)組元素個(gè)數(shù)
    int flag = 0;//
    for (i = 0; i < sz; i++)
    {
        if (k == arr[i])
        {
            flag = 1;
            printf("找到了，下標(biāo)是:%d\n", i);
            break;
        }
    }
    if (flag == 0)
        printf("找不到\n");

???????    return 0;
}

但是這個(gè)代碼的效率比較低，需要循環(huán)多次，所以我們需要用一個(gè)效率較高的方法：二分查找又叫（折半查找）

二分查找的思想

給你一個(gè)有序的序列，取中間元素和目標(biāo)元素進(jìn)行對(duì)比，取其中的一半，丟棄另一半，快速縮小目標(biāo)元素所在的位置。主要思想還是：快速縮小目標(biāo)元素所在的區(qū)間。

二分查找的條件

1.序列必須是有序的，升序或者降序都可以

2. 序列必須是順序存儲(chǔ)元素的，順序存儲(chǔ)元素主要是可以快速的獲取中間元素（可以通過(guò)下標(biāo)來(lái)找到元素）

二分查找的實(shí)現(xiàn)過(guò)程

分析：假設(shè)我們要找的數(shù)字為7，在查找過(guò)程中要用下標(biāo)進(jìn)行查找，此時(shí)我們定義左下標(biāo)為left，右下標(biāo)為right，中間元素下標(biāo)為mid，（left+right）/2=mid。當(dāng)?shù)谝淮尾檎覜](méi)有找到時(shí)，從中間下標(biāo)向左或向右縮短查找范圍繼續(xù)查找，直到找到為止。

以數(shù)字7為例：第一次查找（left+right）/2=（0+9）/2=4，下標(biāo)為4找到的數(shù)字為5，此時(shí)并沒(méi)有找到；第二次查找，因?yàn)閿?shù)字5小于數(shù)字7，所以mid+1=left，right不變，向右查找，此時(shí)（left+right）/2=（5+9）/2=7，下標(biāo)為7，找到的數(shù)字為8，并沒(méi)有找到；第三次查找，因?yàn)閿?shù)字8大于數(shù)字7，所以mid-1=right，左下標(biāo)不變，向左查找，此時(shí)（left+right）/2=（5+6）/2=5，下標(biāo)為5，找到的數(shù)字為6，第四次查找，因?yàn)?小于7，所以向右查找，（left+right）/2=（6+6）/2=6，下標(biāo)為6，找到的數(shù)字為7。

代碼舉例

#include <stdio.h>
int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	// 下標(biāo)       0 1 2 3 4 5 6 7 8 9
	int k = 7;//k是要查找的數(shù)字
	int i = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	//折半查找（二分查找），前提是數(shù)組有序
	int left = 0;
	int right = sz - 1;

	int flag = 0;
	while (left<=right)
	{
		int mid = (left + right) / 2;
		if (arr[mid] < k)
		{
			left = mid + 1;
		}
		else if (arr[mid] > k)
		{
			right = mid - 1;
		}
		else
		{
			printf("找到了，下標(biāo)是：%d\n", mid);
			flag = 1;
			break;
		}
	}
	if (flag == 0)
		printf("找不到\n");

	return 0;
}

如果left是一個(gè)很大的數(shù)，right也是一個(gè)很大的數(shù)，left+right超出整形能表達(dá)的最大值，數(shù)據(jù)溢出，此時(shí)（left+right）/2所求的就不是最大值了這時(shí)要怎么辦呢？

我們讓多出的部分除以二在平分，如圖所示

代碼修改

#include <stdio.h>
int main()
{
	int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
	//            0 1 2 3 4 5 6 7 8 9
	int k = 7;//k是要查找的數(shù)字
	int i = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	//折半查找（二分查找），前提是數(shù)組有序
	int left = 0;
	int right = sz - 1;

	int flag = 0;
	while (left<=right)
	{
		int mid = left + (right - left) / 2;

		if (arr[mid] < k)
		{
			left = mid + 1;
		}
		else if (arr[mid] > k)
		{
			right = mid - 1;
		}
		else
		{
			printf("找到了，下標(biāo)是：%d\n", mid);
			flag = 1;
			break;
		}
	}
	if (flag == 0)
		printf("找不到\n");

	return 0;
}

猜數(shù)字游戲

游戲說(shuō)明

1.電腦生成一個(gè)1~100的的隨機(jī)數(shù)

2.猜數(shù)字

猜大了就告訴你：猜大了

猜小了就告訴你：猜小了

猜對(duì)了就告訴你：恭喜你，猜對(duì)了

猜數(shù)字游戲思想

首先要打印一個(gè)菜單，選擇開(kāi)始游戲還是退出游戲

其次，游戲應(yīng)該可以玩完一局之后玩一局，為循環(huán)進(jìn)行，利用循環(huán)語(yǔ)句構(gòu)建框架

代碼實(shí)現(xiàn)

打印菜單

void menu()
{
    printf("*****************************\n");
    printf("*********   1. play  ********\n");
    printf("*********   0. exit  ********\n");
    printf("*****************************\n");
}

打印結(jié)果

打印主函數(shù)

int main()
{
    int input = 0;
    do
    {
        menu();
        printf("請(qǐng)選擇:>");
        scanf("%d", &input);
        switch (input)
        {
        case 1:
            printf("猜數(shù)字\n");
            break;
        case 0:
            printf("退出游戲\n");
            break;
        default:
            printf("選擇錯(cuò)誤\n");
            break;
        }
    } while (input);
    return 0;
}

此時(shí)游戲過(guò)于簡(jiǎn)單，選擇1要開(kāi)始游戲，所以我們定義一個(gè)游戲函數(shù)game（）

打印游戲函數(shù)

游戲第一步：生成隨機(jī)數(shù)

rand（）函數(shù)為生成隨機(jī)數(shù)函數(shù)，頭文件為<stdlib.h>

rand會(huì)返回一個(gè)0~327637之間的數(shù)

使用rand（）要搭配srand（）一起使用，srand（）是設(shè)置隨機(jī)數(shù)生成器，一般用時(shí)間戳作為時(shí)間的種子，所以使用time函數(shù)來(lái)獲取時(shí)間，然后將time函數(shù)轉(zhuǎn)換為（unsigned)類型在傳給srand函數(shù)

void game()
{
    //1. 生成隨機(jī)數(shù)
    int ret = rand() % 100 + 1;//0~99+1-->1~100
    //2. 猜數(shù)字
    int guess = 0;
    while (1)
    {
        printf("請(qǐng)猜數(shù)字:>");
        scanf("%d", &guess);
        if (guess < ret)
        {
            printf("猜小了\n");
        }
        else if (guess > ret)
        {
            printf("猜大了\n");
        }
        else
        {
            printf("恭喜你，猜對(duì)了\n");
            break;
        }
    }
}

整體代碼演示

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

void menu()
{
	printf("*****************************\n");
	printf("*********   1. play  *******\n");
	printf("*********   0. exit  ********\n");
	printf("*****************************\n");
}
//
//rand函數(shù)會(huì)返回一個(gè)0~32767之間的隨機(jī)數(shù)
//
//時(shí)間戳

void game()
{
	//1. 生成隨機(jī)數(shù)
	int ret = rand() % 100 + 1;//0~99+1-->1~100
	//2. 猜數(shù)字
	int guess = 0;
	while (1)
	{
		printf("請(qǐng)猜數(shù)字:>");
		scanf("%d", &guess);
		if (guess < ret)
		{
			printf("猜小了\n");
		}
		else if (guess > ret)
		{
			printf("猜大了\n");
		}
		else
		{
			printf("恭喜你，猜對(duì)了\n");
			break;
		}
	}
}

int main()
{
	int input = 0;
	//設(shè)置了隨機(jī)數(shù)的生成器
	srand((unsigned int)time(NULL));
    //給srand傳一個(gè)時(shí)間戳，是生成的數(shù)字足夠隨機(jī)
	do
	{
		menu();
		printf("請(qǐng)選擇:>");
		scanf("%d", &input);
		switch (input)
		{
		case 1:
			game();
			break;
		case 0:
			printf("退出游戲\n");
			break;
		default:
			printf("選擇錯(cuò)誤\n");
			break;
		}
	} while (input);
	return 0;
}

游戲效果演示