快捷導(dǎo)航

用C語言實(shí)現(xiàn)二分查找算法

更新時(shí)間：2022年01月17日 15:36:00 作者：banbanbanni

大家好，本篇文章主要講的是c語言實(shí)現(xiàn)二分查找法，感性的同學(xué)趕快來看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽

一.前言

假如今天我們需要在一個(gè)有序的數(shù)組中來尋找一個(gè)數(shù)的下標(biāo)，就用"1，2，3，4，5，6，7，8，9"這九個(gè)數(shù)組成的數(shù)組來說，假如我們想尋找'2'，那很簡(jiǎn)單我們只用從小到大開始尋找，尋找兩次就完成了，但是我們想尋找'7'，我們繼續(xù)用從小到大挨個(gè)尋找，這就顯得有點(diǎn)慢并且耗時(shí)長(zhǎng)還沒有效率，因此我們可以有一種全新的方法，二分查找法來解決這個(gè)問題。

二.二分查找法

1.什么是二分查找法

二分查找法，又叫做折半查找法，它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。就用剛剛的數(shù)組來說，我們想尋找'7'，很簡(jiǎn)單我們先用7和數(shù)組中間的數(shù)來比較大小，很明顯7大于，所以我們縮小范圍，從中間的右邊開始繼續(xù)取中間值，繼續(xù)尋找，直到找到位置，這樣一看找的次數(shù)少了很多，而且速度也快了不少。

2.如何用c語言來實(shí)現(xiàn)二分查找法

咱們來分析一下剛剛我說的找數(shù)字7的過程，首先我們需要數(shù)組的中間的數(shù)也就是中間數(shù)的下標(biāo)值，那我們就需要直到數(shù)組第一個(gè)元素和最后一個(gè)元素的下標(biāo)值，數(shù)組第一個(gè)元素下標(biāo)值很明顯是0，我們把他定義成left；這個(gè)最后一個(gè)元素的下標(biāo)值我們就需要利用sizeof來計(jì)算,我們把他定義成rigth。然后兩個(gè)相加，算出最中間的下標(biāo)，我們把他定義為mid，和要找的數(shù)進(jìn)行比較，假如大于要找的數(shù)那就從mid+1和right之間來繼續(xù)剛剛的循環(huán)，假如小于要找的數(shù)那我們就從left和mid-1之間尋找。就這樣一直循環(huán)，直到找到目標(biāo)數(shù)為止。

代碼的實(shí)現(xiàn)如下

void Findnum(int* arr, int key,int sz)//arr為目標(biāo)數(shù)組，key為需要查找的數(shù),sz為數(shù)組元素的大小
{//二分查找
	int  left = 0;//左邊
	int right = sz-1;//右邊
	while (left <= right)
	{
		int mid = (right + left) / 2;
		if (arr[mid] > key)
		{//說明key在arr[mid]和left之間
			right = mid - 1;
		}
		else if (arr[mid] < key)
		{
			left = mid + 1;
		}
		else
		{
			printf("找到了，對(duì)應(yīng)的下標(biāo)為:%d\n", mid);
			break;
		}
	}
	if (left > right)
	{
		printf("找不到\n");
	}
}

最后運(yùn)行

三.總結(jié)

關(guān)于上面的過程，我們不難發(fā)現(xiàn)二分查找法雖然很快，但是有兩個(gè)很明顯的缺點(diǎn)，一個(gè)是他實(shí)現(xiàn)的條件必須是一個(gè)有序的數(shù)列，另外一個(gè)是他只能一次性找一個(gè)數(shù)而不是多個(gè)，這就讓他有了很多局限性。二分查找有個(gè)很重要的特點(diǎn)，就是不會(huì)查找數(shù)列的全部元素，而查找的數(shù)據(jù)量其實(shí)正好符合元素的對(duì)數(shù)，正常情況下每次查找的元素都在一半一半地減少。所以二分查找的時(shí)間復(fù)雜度為

log2o是毫無疑問的。