引入二分查找

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

先給大家提出一個問題

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

我想一定是會說1000，他說太少了，你又猜1500…

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

接下來我們來看一個問題

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

有一部分帥氣的觀眾可能會說:

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

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

那如果數(shù)組中有幾十萬個呢？

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

分析二分查找

我們用一個簡單的實例來實現(xiàn)一下二分查找

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

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

我們在其中查找一個數(shù)字。使用二分查找，我們?nèi)绾未_定中間值呢？

有人說，數(shù)組長度除以二，但是中間值會變，數(shù)組長度不可變 ----排除

這邊我們給大家?guī)韮煞N方法來計算中間值

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

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

第一種

mid = (left + right) / 2;

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

第二種

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

我們得想辦法解決掉這個問題

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

、

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

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

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

代碼實現(xiàn)

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

還有一個問題,什么時候就不再查找了呢？

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

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

話不多說，直接上代碼

#include <stdio.h>
//詳解二分查找
int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	//計算數(shù)組長度
	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é)

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

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

大家下來一定要自己畫圖理解，寫代碼測試，多寫寫就悟了。

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

最新評論