1. 題目描述

N 個有序整數(shù)數(shù)列已放在一維數(shù)組中，利用二分查找法查找整數(shù) m 在數(shù)組中的位置。

若找到，則輸出其下標(biāo)值；反之，則輸出 “ Not be found！”。

2. 問題分析

二分查找法（也叫折半查找）其本質(zhì)是分治算法的一種。

所謂分治算法是指的分而治之，即將較大規(guī)模的問題分解成幾個較小規(guī)模的問題，這些子問題互相獨立且與原問題相同，通過對較小規(guī)模問題的求解達到對整個問題的求解。

我們把將問題分解成兩個較小問題求解的分治方法稱為二分法。需要注意的是，二分查找法只適用于有序序列。

二分查找的基本思想是：每次查找前先確定數(shù)組中待查的范圍，假設(shè)指針 low 和 high (low<high) 分別指示待查范圍的 下界 和 上界，指針 mid 指示區(qū)間的 中間位置，即 mid=(low+high)/2，把 m 與 中間位置 (mid) 中元素的值進行比較。

如果m的值大于中間位置元素中的值，則下一次的查找范圍放在中間位置之后的元素中；

反之，下一次的查找范圍放在中間位置之前的元素中。直到 low>high，查找結(jié)束。

3. 算法設(shè)計

N 個有序數(shù)應(yīng)存放在數(shù)組中，根據(jù)數(shù)組下標(biāo)的取值范圍知指針 low 和 high 的初值分別為 0、N-1。

除了三個指針變量 low、high、mid 之外還需要一個變量（假設(shè)為 k）來 記錄下標(biāo)，利用變量 k 的值來 判斷整數(shù)是否在所給出的數(shù)組中。下面我們用示意圖來表示二分查找的過程。

假設(shè)一維數(shù)組中存儲的有序數(shù)列為：5 13 19 21 37 56 64 75 80 88 92，要查找的整數(shù) m 為 21。

根據(jù)二分查找方法可知指針 low 和 high 最初分別指向元素 5 和 92，由 mid=(low+high)/2 知，指針 mid 指向元素 56。示意圖如下：

變量 m 所代表的整數(shù) 21 與 指針 mid 所指的元素 56 進行比較， 21 小于 56， 根據(jù)二分查找算法知， 查找范圍現(xiàn)在縮小到指針 mid 所指元素的前面， 即從 5~37 的范圍。

指針 high 原來指向下標(biāo)為 N-1 的元素，現(xiàn)在指向下標(biāo)為 mid-1 的元素，接著重新計算指針 mid 所指元素的下標(biāo)。

再次進行比較，21 大于 19，現(xiàn)在比較范圍再次轉(zhuǎn)移到 mid 所指元素的后面，low 元素所指元素下標(biāo)由 0 變?yōu)?mid+1。

當(dāng)前 mid 所指元素的值為 21，與要查找的整數(shù)值相同，因此查找成功，所查元素在表中序號等于指針 mid 的值。

4. 動圖演示

動圖解析

5. 代碼實現(xiàn)

流程圖設(shè)計

完整代碼

#include <stdio.h>
#define N 10

int main()
{
	int a[N] = { -3,4,7,9,13,45,67,89,100,180 }; 
	int low = 0; 
	int high = N - 1; 
	int mid; 
	int i;
	int m; 
	int k = -1;

	printf("a 數(shù)組中的數(shù)據(jù)如下：");
	for (i = 0; i < N; i++)
	{
		printf("%d ", a[i]); 
	}

	printf("\n");

	printf("Enter m：");
	scanf("%d", &m); 

	while (low <= high) 
	{
		mid = (low + high) / 2; 

		if (m < a[mid])
		{
			high = mid - 1;
		}
		else
		{
			if (m > a[mid])
			{
				low = mid + 1;
			}
			else
			{
				k = mid;
				break; 
			}
		}
	}
	if (k >= 0)
		printf("m=%d index=%d\n", m, k);
	else
		printf("Not be found!\n");
}

運行結(jié)果

代碼貼圖

程序分析

在上述程序中循環(huán)結(jié)束可以有兩種情況。

一種是由于循環(huán)的判定條件 low <= high 不成立的情況下跳出循環(huán)，此時可知查找不成功。

在查找不成功的情況下，語句 else {k=mid; break;} 是不執(zhí)行的，所以變量 k 的值不變?nèi)詾槌踔?-1。

第二種結(jié)束循環(huán)的情況是由于執(zhí)行了 break; 語句而跳出循環(huán)，在此情況下，變量 k 的值由 -1 變成了一個大于等于 0 的數(shù)，即指針 mid 所指元素的下標(biāo)值。

所以在最后用選擇結(jié)構(gòu)來判定 k 的值，從而確定整個查找過程是否成功。

6.知識點補充

continue 語句

continue 語句的格式為：

continue;

continue 語句用于循環(huán)語句（while循環(huán)語句 或 do...while循環(huán)語句 或 for循環(huán)語句）中，作為循環(huán)體的一部分。

在程序執(zhí)行時，一旦遇到了 continue 語句，則立即結(jié)束本次循環(huán)，即跳過循環(huán)體中 continue 后面尚未執(zhí)行的語句，接著進行是否繼續(xù)循環(huán)的條件判定。

break 語句

break 語句的格式如下：

break;

break 語句 可用在 switch 語句中。

在程序執(zhí)行時， 一旦遇到了 break 語句， 則立即退出當(dāng)前的 switch 語句。

除此之外， break 語句還能用于循環(huán)語句（while循環(huán)語句 或 do...while 循環(huán)語句 或 for 循環(huán)語句)）中， 作為循環(huán)體的一部分。

在程序執(zhí)行時， 一旦遇到了 break語句， 則立即退出當(dāng)前的循環(huán)體，接著執(zhí)行當(dāng)前循環(huán)體下面的語句。

continue語句 和 break語句的區(qū)別

continue 只是結(jié)束本次循環(huán)，不再執(zhí)行循環(huán)體中 continue 后面的其余語句，并不是終止當(dāng)前循環(huán)。

break 是直接終止當(dāng)前的循環(huán)。

7. 問題拓展

在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找某個指定的元素，通常根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，應(yīng)采用不同的查找方法。對于一個有序數(shù)列，除了采用二分查找法之外還可以采用 順序查找 的方法。

順序查找一般是指 在線性表中查找指定的元素，其基本方法如下：

從線性表的第一個元素開始，依次將線性表的元素與被查元素進行比較，若相等則表示找到即查找成功；

若線性表中所有的元素都與被查元素進行了比較但都不相等，則表示線性表中沒有要找的元素即查找失敗。

在長度為 n 的線性表中查找指定元素，最好的情況是比較一次成功，最壞的情況是比較 n 次，平均要比較(1＋2＋3＋⋅⋅⋅＋n)/n＝(1＋n)/2 次。

盡管順序查找的效率低，但對于一些情況只能采用順序查找的方法，如對于一個無序表進行查找。

完整代碼

#include <stdio.h>
#define N 10

int main()
{
	int a[N] = { -3,4,7,9,13,45,67,89,100,180 }, i, m, k = -1;
	printf("a數(shù)組中的數(shù)據(jù)如下: ");
	for (i = 0; i < N; i++)
	{
		printf("%d ", a[i]); //輸出數(shù)組中原數(shù)據(jù)序列
	}

	printf("\n");

	printf("Enter m: ");
	scanf("%d", &m); //由鍵盤輸入要查找的整數(shù)值

	for (i = 0; i < N; i++)
	{
		if (m == a[i])
		{
			k = i;
			break; //一旦找到所要查找的元素便跳出循環(huán)
		}
	}

	if (k >= 0)
		printf("%m=%d index=%d\n", m, k);
	else
		printf("Not be found!\n");

	return 0;
}

運行結(jié)果

到此這篇關(guān)于C語言算法練習(xí)之折半查找的實現(xiàn)的文章就介紹到這了,更多相關(guān)C語言折半查找內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論