快捷導(dǎo)航

C語(yǔ)言編程之初識(shí)數(shù)組線性查找和二分查找

更新時(shí)間：2021年09月17日 14:43:02 作者：Booksort

本篇文章是C語(yǔ)言編程篇，主要為大家介紹C語(yǔ)言編程中數(shù)組的線性查找及二分查找分析講解，有需要的朋友可以借鑒參考下，希望可以有所幫助

線性查找

線性查找與二分查找有些差別。
數(shù)組內(nèi)元素可以是混亂無(wú)序的，即沒(méi)有按順序儲(chǔ)存。這方法很簡(jiǎn)單，就是從首元素開始，依此向后查找，比較。僅此而已。運(yùn)用循環(huán)，依次對(duì)比。
看代碼吧。

#include <stdio.h>
int main(void)
{
	int arr[] = { 5,4,6,8,7,9,10,2,3,1 };
	int len = sizeof(arr) / sizeof(arr[0]);//計(jì)算數(shù)組的元素個(gè)數(shù)
	int i;
	int n;
	scanf("%d", &n);//輸入要查找的元素
	for (i = 0; i < len; i++)
	{
		if (arr[i] == n)
		{
			printf("%d的下標(biāo)是%d\n", n, i);
			break;//找到后就直接跳出循環(huán)
		}
	}
	if (i == len)//因?yàn)槿绻麛?shù)組元素全部遍歷一遍后，都沒(méi)有i++等于len后，便跳出循環(huán)再判斷說(shuō)不存在。
		printf("Don't have number %d\n", n);	
	return 0;
}

線性查找非常簡(jiǎn)單但，要是數(shù)組元素較大，就比較麻煩，畢竟要一個(gè)個(gè)遍歷過(guò)去時(shí)間復(fù)雜度為n。

二分查找

來(lái)看看二分查找，就是高中數(shù)學(xué)學(xué)到過(guò)的二分法，原理相當(dāng)簡(jiǎn)單。但是它只能查找已經(jīng)排序好的數(shù)組，與線性查找相比，有些局限性。
通過(guò)比較數(shù)組中間數(shù)據(jù)與目標(biāo)數(shù)據(jù)的大小，來(lái)判斷是在中間數(shù)據(jù)的左邊還是右邊，瞬間縮小一半的運(yùn)算量。再按照這種繼續(xù)比較，直到找到或找不到為止。

#include <stdio.h>
int main(void)
{
	int n;
	scanf("%d", &n);
	int arr[] = { 1,2,3,4,5,6,7,8,9,10};
	int len = sizeof(arr) / sizeof(arr[0]);
	int left = 0;
	int right = len - 1;
	int mid;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (arr[mid] > n)
		{
			right = mid-1;
		}
		else if (arr[mid] < n)
		{
			left = mid+1;
		}
		else 
		{
			break;
		}
	}
	if (left <= right)
		printf("%d的下標(biāo)是%d\n", n, mid);
	else 
		printf("DON't have number %d\n", n);
	return 0;
}
	/*int i = 1;

看張圖吧，方便理解與記憶。

在這里插入圖片描述

看代碼中的，中間元素是5，在5的右邊，再把不需要的元素移出比較范圍，再，重新設(shè)置中間元素，進(jìn)行比較。

在這里插入圖片描述

再拿8進(jìn)行比較，在8左邊。重新規(guī)劃范圍。

在這里插入圖片描述

7比6大，則在6右邊，繼續(xù)比較。

在這里插入圖片描述

此時(shí)，left==right,跟據(jù)while循環(huán)條件，依舊可以進(jìn)入循換,但arr[mid]7,說(shuō)明已經(jīng)找到那個(gè)元素，會(huì)break;跳出循環(huán)，再判斷條件滿足left<=right，說(shuō)明依舊成立，就輸出。
否則，如果目標(biāo)元素是11，則一直會(huì)是中間元素的右邊。

在這里插入圖片描述

再left=MID+1就是10,此時(shí)，leftright，循環(huán)還沒(méi)結(jié)束，這一次，mid等于10還是比11小，left=10+1,而此時(shí)，left>right，不符合條件，循環(huán)結(jié)束，再判斷，不符合條件，就進(jìn)入else，，說(shuō)明，11不在數(shù)組內(nèi)。
我第一次寫二分查找時(shí)，沒(méi)有寫

left = mid+1;
right = mid-1;

而是寫

right = mid;
left = mid;

本以為差不多，額，事實(shí)上確實(shí)差不多，不過(guò)當(dāng)目標(biāo)數(shù)據(jù)不在數(shù)組內(nèi)時(shí)，要提前判斷。如果直接以上面代碼的形式，改條件，就會(huì)造成，left一直是9,right一直是10，mid也一直是9，無(wú)法跳出循環(huán)，造成這樣的死循環(huán)局面。
當(dāng)寫二分查找時(shí)一定要切記。
這兩個(gè)查護(hù)，目前就這些。
如有問(wèn)題，煩請(qǐng)大佬指點(diǎn)一二。
謝謝觀看。

以上就是C語(yǔ)言編程之初識(shí)數(shù)組線性查找和二分查找的詳細(xì)內(nèi)容，更多關(guān)于C語(yǔ)言數(shù)組的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: