查找

前言

在我們?nèi)粘Ｉ钪?，?jīng)常會(huì)遇到查找一樣?xùn)|西的情景，比如在一個(gè)班的學(xué)生成績(jī)中找到xx分對(duì)應(yīng)的人

我們可以嘗試用c語(yǔ)言程序解決這類查找問(wèn)題

#include<stdio.h>
int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	int k = 7;//被查找的元素
	int i = 0;
	for (i = 0; i < 10; i++)//遍歷數(shù)組
	{
		if (arr[i] == k)
		{
			printf("找到了，下標(biāo)是%d", i);
		}
	}
	return 0;
}

我們可以很容易寫出這樣的代碼

這里數(shù)組arr中只有十個(gè)元素，那如果有100個(gè)，1000個(gè)，100000000…000個(gè)呢？

考慮最壞的情況，我們所要找的元素正好處在數(shù)組的最后一個(gè)，那就意味著我們的循環(huán)要進(jìn)行n次（當(dāng)存在n個(gè)元素時(shí)）

這樣程序的效率就會(huì)很低。

那我們有沒有更好的查找方法呢？

當(dāng)然有，就是我們今天要提到的二分查找。

那么二分查找是什么意思呢？

首先二分查找的前提是被查找的數(shù)組必須是有序的

例如

我們首先記錄數(shù)組最左端的下標(biāo)為left，最右邊的為right。
求出中間元素的下標(biāo)mid=（left+right）/2
判斷被查找的元素(定義為k)和中間元素的大小

如果arr[mid]>k
意思是中間元素的值大于被查找的元素，那么k就只能在中間元素的左側(cè)，因?yàn)閿?shù)組是有序的。

同理如果arr[mid]<k
意思是中間元素的值小于被查找的元素，那么k就只能在中間元素的右側(cè)，因?yàn)閿?shù)組是有序的。

如果arr[mid]=k
w這就意味著我們找到了被查找的數(shù)

這樣我們其實(shí)就完成了一次二分查找

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

#include<stdio.h>
int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	int left = 0, right = 9;//數(shù)組左邊下標(biāo)為left，右邊下標(biāo)為right
	int mid = 0;//定義數(shù)組中間元素下標(biāo)為mid
	int k = 7;//定義待查找的數(shù)；
	mid = (right + left) / 2;
	if (arr[mid] < k)
	{
		left = mid + 1;
	}
	else if (arr[mid] > k)
	{
		right = mid - 1;
	}
	else
	{
		printf("找到了，下標(biāo)是：%d", mid);//如果查找到元素，打印該元素下標(biāo)；
	}

	return 0;
}

但是我們往往不能在一次查找中就把被查找的元素找到

所以我們?nèi)绻胍獪?zhǔn)確查找出被查找的元素，就應(yīng)該還需要繼續(xù)進(jìn)行這樣的查找，所以我們將上述過(guò)程放在一個(gè)循環(huán)中

那么循環(huán)的條件是什么呢？

int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };

我們拿這個(gè)數(shù)組舉例，假設(shè)我們被查找的數(shù)是k=7；
我們可以得到
left=0 right=9 mid=(0+9)/2=4
下標(biāo)4對(duì)應(yīng)的元素是5 5<7 所以將5右邊的元素全部排除 left=mid+1=5
現(xiàn)在沒有查找到，再來(lái)一次

left=5 right=9 mid=(5+9)/2=7

arr[7]=8 >被查找的元素k right=mid-1=6

left=5 right=6 mid=(5+6)/2=5 *

arr[5]=6 < 被查找的元素 left=mid-1=6

left=6 right=6此時(shí)left=right;

arr[6]=7=k 該元素被查找到 說(shuō)明其中其中一個(gè)條件是left=right

如果我要找的元素在這個(gè)序列中并，沒有出現(xiàn) 那么就會(huì)出現(xiàn)left>right的情況（可以按照上述的分析方法分析）

所以循環(huán)的條件是left<=right

代碼如下

#include<stdio.h>
int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	int left = 0, right = 9;//數(shù)組左邊下標(biāo)為left，右邊下標(biāo)為right
	int mid = 0;//定義數(shù)組中間元素下標(biāo)為mid
	int k = 0;
	scanf("%d", &k);//定義待查找的數(shù)；
	int flag = 1;//標(biāo)志變量
	
	while (left <= right)
	{
		mid = (right + left) / 2;
		if (arr[mid] < k)
		{
			left = mid + 1;
		}
		else if (arr[mid] > k)
		{
			right = mid - 1;
		}
		else
		{
			flag = 0;
			printf("找到了，下標(biāo)是：%d", mid);//如果查找到元素，打印該元素下標(biāo)；
			break;//找到元素，跳出循環(huán)；
		}
	}
	if (flag == 1)
	{
		printf("找不到");
	}
	return 0;
}

到此我們就實(shí)現(xiàn)了二分查找
如果認(rèn)為這篇博客對(duì)你有幫助，留下你的點(diǎn)贊和關(guān)注吧！

本文所使用IDE VS2022文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-470453.html

到了這里，關(guān)于【C語(yǔ)言】二分查找的實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！