先來了解一下什么是查找，
額，好吧，這沒什么可了解的，
就是查找數(shù)組中的某個元素的位置或是否存在。
就這，沒了。直接了解查找算法吧。

線性查找

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

#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]);//計算數(shù)組的元素個數(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ù)組元素全部遍歷一遍后，都沒有i++等于len后，便跳出循環(huán)再判斷說不存在。
		printf("Don't have number %d\n", n);	
	return 0;
}

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

二分查找

來看看二分查找，就是高中數(shù)學(xué)學(xué)到過的二分法，原理相當(dāng)簡單。但是它只能查找已經(jīng)排序好的數(shù)組，與線性查找相比，有些局限性。
通過比較數(shù)組中間數(shù)據(jù)與目標(biāo)數(shù)據(jù)的大小，來判斷是在中間數(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ù)比較。

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

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

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

而是寫

right = mid;
left = mid;

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

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

最新評論