快捷導(dǎo)航

C語(yǔ)言折半查找法的由來(lái)及使用詳解

更新時(shí)間：2022年08月18日 11:14:44 作者：Zoroxs

折半查找法也叫做?分查找,顧名思義就是把數(shù)據(jù)分成兩半,再判斷所查找的key在哪?半中,再重復(fù)上述步驟知道找到?標(biāo)key,下面這篇文章主要給大家介紹了關(guān)于C語(yǔ)言折半查找法的相關(guān)資料,需要的朋友可以參考下

引入二分查找

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

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

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

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

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

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

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

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

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

但是大家有沒(méi)有想過(guò)一個(gè)問(wèn)題，數(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)行了分析，這種方法并沒(méi)有漏過(guò)任何一個(gè)數(shù)，所以可以使用

第二種

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

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

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

、

把這種方法寫(xiě)成表達(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è)問(wèn)題,什么時(shí)候就不再查找了呢？

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

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

話不多說(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;
}