引入二分查找

本文帶著大家學(xué)習(xí)一個(gè)簡(jiǎn)單的**二分查找算法，也叫折半查找算法**

先給大家提出一個(gè)問題

額，大家應(yīng)該都會(huì)碰到這種情況，那大家怎么猜呢？

我想一定是會(huì)說(shuō)1000，他說(shuō)太少了，你又猜1500…

這其實(shí)就是二分查找的應(yīng)用。

接下來(lái)我們來(lái)看一個(gè)問題

如何在一個(gè)有序數(shù)組中查找一個(gè)數(shù)字？

有一部分帥氣的觀眾可能會(huì)說(shuō):

直接遍歷數(shù)組，一個(gè)一個(gè)對(duì)比就找到了啊

但是大家有沒有想過一個(gè)問題，數(shù)組中如果只有幾十個(gè)數(shù)的話，那完全可以這樣做

那如果數(shù)組中有幾十萬(wàn)個(gè)呢？

這樣遍歷絕對(duì)是非常消耗時(shí)間，題目很明確說(shuō)有序數(shù)組，如果直接遍歷，我們是不是對(duì)不起有序這二字呢？

分析二分查找

我們用一個(gè)簡(jiǎn)單的實(shí)例來(lái)實(shí)現(xiàn)一下二分查找

比如有這樣一個(gè)數(shù)組

計(jì)算中間下標(biāo)的兩種方法

我們?cè)谄渲胁檎乙粋€(gè)數(shù)字。使用二分查找，我們?nèi)绾未_定中間值呢？

有人說(shuō)，數(shù)組長(zhǎng)度除以二，但是中間值會(huì)變，數(shù)組長(zhǎng)度不可變 ----排除

這邊我們給大家?guī)?lái)兩種方法來(lái)計(jì)算中間值

首先大家要清楚，我們要有兩個(gè)邊界，就是范圍，比如鞋子02000變成10002000

我們使用兩個(gè)下標(biāo)作為兩端，left 以及 right 中間值我們定義為mid

第一種

mid = (left + right) / 2;

我對(duì)長(zhǎng)度為奇數(shù)和偶數(shù)的數(shù)組都進(jìn)行了分析，這種方法并沒有漏過任何一個(gè)數(shù)，所以可以使用

第二種

第一種方法有一種弊病，如果數(shù)組特別長(zhǎng)的話，left+right可能會(huì)超出類型的最大值范圍

我們得想辦法解決掉這個(gè)問題

假如我們把left最上邊那一小塊放到left上邊，是不是就是中間值了呢

、

把這種方法寫成表達(dá)式就是

mid = (right - left) / 2 + left;

這就是兩種計(jì)算中間下標(biāo)的方法

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

• 當(dāng)mid處的值 < 待查找的值的時(shí)候 ，需要把 mid處的以及前邊的舍棄,即left右移， left = mid +1;
• 當(dāng)mid處的值 > 待查找的值的時(shí)候 ，需要把 mid處的以及后邊的舍棄,即right左移，right = mid -1;
• 當(dāng)相等時(shí)，便不再查找。

還有一個(gè)問題,什么時(shí)候就不再查找了呢？

• left < right 時(shí)，中間仍有數(shù)據(jù)未查找
• left = right 時(shí)，有一個(gè)數(shù)未比較
• left>right 時(shí)，都找完了，沒找到

所以當(dāng)left > right 時(shí)，就沒必要查找了

話不多說(shuō)，直接上代碼

#include <stdio.h>
//詳解二分查找
int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	//計(jì)算數(shù)組長(zhǎng)度
	int length = sizeof(arr) / sizeof(arr[0]);
	int n = 0;//待查找的值
	scanf("%d", &n);
	int left = 0;//左下標(biāo)
	int right = length - 1;//右下標(biāo)
	int mid = 0;//中間下標(biāo)
	while(left <= right)
	{
		mid = (left + right) / 2;
		if(arr[mid] > n)
		{
			right = mid - 1;
		}
		else if (arr[mid] < n)
		{
			left = mid + 1;
		}
		else
		{
			printf("找到了，下標(biāo)為%d\n", mid);
			break;
		}
	}
	if (left > right)
	{
		printf("找不到，數(shù)組中不存在該值\n");
	}
	return 0;
}

總結(jié)

理解二分查找法的實(shí)現(xiàn)方式

核心在于中間下標(biāo)的控制以及下標(biāo)的變化

大家下來(lái)一定要自己畫圖理解，寫代碼測(cè)試，多寫寫就悟了。

到此這篇關(guān)于C語(yǔ)言折半查找法的由來(lái)及使用詳解的文章就介紹到這了,更多相關(guān)C語(yǔ)言折半查找內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！