快捷導(dǎo)航

C語(yǔ)言二分查找圖文詳解

更新時(shí)間：2023年04月27日 08:42:38 作者：北飛的山羊

折半查找法也叫做二分查找,顧名思義就是把數(shù)據(jù)分成兩半,再判斷所查找的key在哪一半中,再重復(fù)上述步驟知道找到目標(biāo)key,這篇文章主要給大家介紹了關(guān)于C語(yǔ)言二分查找的相關(guān)資料,需要的朋友可以參考下

一、二分查找算法

所謂二分查找，就是要在一組有序的數(shù)列中，查找給定的數(shù)是否在此數(shù)列中。

最主要的步驟有三個(gè)：

1.確定被查找的范圍的左右下標(biāo)left、right
2.根據(jù)left和right，確定中間元素的下標(biāo)mid
3.根據(jù)mid鎖定的元素和查找的元素比較，確定新的查找范圍left和right

下面將用圖示和代碼來(lái)講解上面的三個(gè)步驟：

1.假定給定的數(shù)組中元素個(gè)數(shù)為奇數(shù)個(gè)

2.假定給定的數(shù)組為偶數(shù)個(gè)

3.假定給定的數(shù)不在此數(shù)列中

根據(jù)以上這三種情況，代碼可以寫(xiě)成如下形式：

#include <stdio.h>
int main()
{
    int arr[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13 };
    int left = 0, right = sizeof(arr) / sizeof(arr[0]) - 1;
    int x = 0,flag = 0;
 
    scanf("%d", &x);//要找的數(shù)
 
    while (left <= right)//若要找的數(shù)在此數(shù)組中，此條件會(huì)一直成立；
                         //若要找的數(shù)不在此數(shù)組中，最終left會(huì)大于right,從循環(huán)中跳出
    {
        int mid = (left + right) / 2;
        if (x == arr[mid])
        {
            printf("%d\n", mid);
            flag = 1;
            break;
        }
        else if (x > arr[mid])
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    if (flag == 0)//只有當(dāng)要找的數(shù)在數(shù)組中找不到時(shí)flag == 0
    {
        printf("找不到\n");
    }
    return 0;
}

總結(jié)：從上面的例子可以看出，二分法求解是一種很高效的方法，因?yàn)橐淮尉涂梢耘懦话氲目赡苄浴?strong>但也要注意，二分法只適用于有序數(shù)列

二、分支語(yǔ)句中應(yīng)注意的小點(diǎn)

1.懸空else語(yǔ)句

#include <stdio.h>
int main()
{
	int a = 0;
	int b = 2;
	if (a == 1)
		if (b == 2)
			printf("hehe\n");
		else
			printf("haha\n");
	return 0;
}

在上面的代碼中，有人可能就會(huì)對(duì)else語(yǔ)句與哪個(gè)if語(yǔ)句配對(duì)產(chǎn)生誤解。

其實(shí)：else是和它離的最近的if匹配的。但如果是像上面那樣寫(xiě)就容易引起歧義?？梢詫?xiě)成下面的形式：

#include <stdio.h>
int main()
{
	int a = 0;
	int b = 2;
	if (a == 1)
	{
		if (b == 2)
		{
			printf("hehe\n");
		}
	}
	else
	{
		printf("haha\n");
	}
	return 0;
}

適當(dāng)?shù)氖褂脅}可以使代碼的邏輯更加清楚。

2.switch語(yǔ)句中的break

switch允許嵌套使用

#include <stdio.h>
int main()
{
	int n = 1;
	int m = 2;
	switch (n)
	{
	case 1:
		m++;//m == 3
	case 2:
		n++;//n == 2
	case 3:
		switch (n)
		{//switch允許嵌套使用
		case 1:
			n++;
		case 2:
			m++;//m == 4
			n++;//n == 3
			break;
		}
	case 4:
		m++;//m == 5, n == 3
		break;
	default:
		break;
	}
	printf("m = %d, n = %d\n", m, n);
	return 0;
}

上面代碼中，有的case語(yǔ)句后沒(méi)有加上break,這就會(huì)導(dǎo)致執(zhí)行完一條沒(méi)有加break的case語(yǔ)句后還會(huì)執(zhí)行其下面的一條case語(yǔ)句，可能就會(huì)導(dǎo)致跟我們想要的判斷輸出結(jié)果不同。因?yàn)閟witch更多時(shí)候執(zhí)行的是條件判斷的功能，所以最好