C語言通過二分查找實現猜數字游戲

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

這篇文章主要為大家詳細介紹了在C語言中如何通過二分查找思想編寫一個簡單的猜數字游戲，文中的示例代碼講解詳細，感興趣的小伙伴可以跟隨小編一起學習一下

二分查找

題目：在一個有序數組中查找具體的某個數字n。

首先我們先定義一個1···10的數組，如果7為我們要查找的數字，編寫代碼如下

#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是要查找的數字
    int i = 0;
    int sz = sizeof(arr) / sizeof(arr[0]);
     //sz為數組元素個數
    int flag = 0;//
    for (i = 0; i < sz; i++)
    {
        if (k == arr[i])
        {
            flag = 1;
            printf("找到了，下標是:%d\n", i);
            break;
        }
    }
    if (flag == 0)
        printf("找不到\n");

???????    return 0;
}

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

二分查找的思想

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

二分查找的條件

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

2. 序列必須是順序存儲元素的，順序存儲元素主要是可以快速的獲取中間元素（可以通過下標來找到元素）

二分查找的實現過程

分析：假設我們要找的數字為7，在查找過程中要用下標進行查找，此時我們定義左下標為left，右下標為right，中間元素下標為mid，（left+right）/2=mid。當第一次查找沒有找到時，從中間下標向左或向右縮短查找范圍繼續(xù)查找，直到找到為止。

以數字7為例：第一次查找（left+right）/2=（0+9）/2=4，下標為4找到的數字為5，此時并沒有找到；第二次查找，因為數字5小于數字7，所以mid+1=left，right不變，向右查找，此時（left+right）/2=（5+9）/2=7，下標為7，找到的數字為8，并沒有找到；第三次查找，因為數字8大于數字7，所以mid-1=right，左下標不變，向左查找，此時（left+right）/2=（5+6）/2=5，下標為5，找到的數字為6，第四次查找，因為6小于7，所以向右查找，（left+right）/2=（6+6）/2=6，下標為6，找到的數字為7。

代碼舉例

#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是要查找的數字
	int i = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	//折半查找（二分查找），前提是數組有序
	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("找到了，下標是：%d\n", mid);
			flag = 1;
			break;
		}
	}
	if (flag == 0)
		printf("找不到\n");

	return 0;
}

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

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

代碼修改

#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是要查找的數字
	int i = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	//折半查找（二分查找），前提是數組有序
	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("找到了，下標是：%d\n", mid);
			flag = 1;
			break;
		}
	}
	if (flag == 0)
		printf("找不到\n");

	return 0;
}

猜數字游戲

游戲說明

1.電腦生成一個1~100的的隨機數

2.猜數字

猜大了就告訴你：猜大了

猜小了就告訴你：猜小了

猜對了就告訴你：恭喜你，猜對了

猜數字游戲思想

首先要打印一個菜單，選擇開始游戲還是退出游戲

其次，游戲應該可以玩完一局之后玩一局，為循環(huán)進行，利用循環(huán)語句構建框架

代碼實現

打印菜單

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

打印結果

打印主函數

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

此時游戲過于簡單，選擇1要開始游戲，所以我們定義一個游戲函數game（）

打印游戲函數

游戲第一步：生成隨機數

rand（）函數為生成隨機數函數，頭文件為<stdlib.h>

rand會返回一個0~327637之間的數

使用rand（）要搭配srand（）一起使用，srand（）是設置隨機數生成器，一般用時間戳作為時間的種子，所以使用time函數來獲取時間，然后將time函數轉換為（unsigned)類型在傳給srand函數

void game()
{
    //1. 生成隨機數
    int ret = rand() % 100 + 1;//0~99+1-->1~100
    //2. 猜數字
    int guess = 0;
    while (1)
    {
        printf("請猜數字:>");
        scanf("%d", &guess);
        if (guess < ret)
        {
            printf("猜小了\n");
        }
        else if (guess > ret)
        {
            printf("猜大了\n");
        }
        else
        {
            printf("恭喜你，猜對了\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函數會返回一個0~32767之間的隨機數
//
//時間戳

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

int main()
{
	int input = 0;
	//設置了隨機數的生成器
	srand((unsigned int)time(NULL));
    //給srand傳一個時間戳，是生成的數字足夠隨機
	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;
}

游戲效果演示