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

本文小編為大家詳細介紹“C語言怎么通過二分查找實現猜數字游戲”，內容詳細，步驟清晰，細節處理妥當，希望這篇“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;
}

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

二分查找的思想

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

二分查找的條件

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

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

二分查找的實現過程

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

以數字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.猜數字

猜大了 就告訴你：猜大了

猜小了 就告訴你：猜小了

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

猜數字游戲思想

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

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

代碼實現

打印菜單

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;
}

游戲效果演示

讀到這里，這篇“C語言怎么通過二分查找實現猜數字游戲”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。