1. 二分查找思想

二分法：二分查找算法是一種在有序數(shù)組中查找某一特定元素的搜索算法，其思想就是不斷地將有序查找表“一分為二”，逐漸縮小搜索區(qū)域，進(jìn)而找到目標(biāo)元素。

• 搜素過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜 素過程結(jié)束；
• 如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。
• 如果在某一步驟數(shù)組 為空，則代表找不到。
• 這種搜索算法每一次比較都使搜索范圍縮小一半。折半搜索每次把搜索區(qū)域減少一半，時(shí)間復(fù)雜度為Ο(logn) 。

注：使用二分查找的前提條件是，數(shù)組已經(jīng)是有序的

二分查找圖解：以有序數(shù)組 {10, 14, 19, 26, 27, 31, 33, 35, 42, 44} 為例，查找元素 33。

初始狀態(tài)：

第一輪查找：根據(jù) 27<33，可以判定 33 位于 27 右側(cè)的區(qū)域，更新搜索區(qū)域?yàn)樵?27 右側(cè)的區(qū)域。

第二輪查找：35>33，可以判定 33 位于 35 左側(cè)的區(qū)域，更新搜索區(qū)域。

第三輪查找：31<33，可以判定 33 位于 31 右側(cè)的區(qū)域，更新搜索區(qū)域。

第四輪查找：搜索區(qū)域內(nèi)中間元素的位置是 [(7+7)/2]=7，因此中間元素是 33，此元素就是要找的目標(biāo)元素。

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

2.1 未封裝函數(shù)

代碼實(shí)現(xiàn)思路：

• 定義low、high、mid，分別代表最小值、最大值和中間值的下標(biāo)，并且初始賦值low指向第一個(gè)元素，high指向最后一個(gè)元素；定義target代表要查找的目標(biāo)值。
• 進(jìn)行循環(huán)二分查找，循環(huán)的條件是左邊界還未超過右邊界(low <= high)，當(dāng)左邊界超過右邊界，說明查找結(jié)束了。
• 對(duì)比目標(biāo)值與中間值的大小，如果兩者相等說明查找到了（該值的下標(biāo)就是中間值的下標(biāo)mid）；如果目標(biāo)值大于中間值，說明目標(biāo)值在左半邊，此時(shí)縮小右邊界的范圍 (high = mid - 1)重新查找；如果目標(biāo)值小于中間值，說明目標(biāo)值在右半邊，此時(shí)縮小左邊界的范圍 (low = mid + 1)重新查找。

#include <stdio.h>
#define N 11

int main() 
{
	int a[N] = {1, 5, 8, 11, 19, 22, 31, 35, 40, 49, 50}; // 準(zhǔn)備好一個(gè)已經(jīng)排序好的數(shù)組
	int low = 0, high = N - 1, mid, target; 
	printf("請(qǐng)輸入要查找的值：");
	scanf("%d", &target);
	printf("%d\n", target);
	
	// 當(dāng)左邊界還未超過右邊界時(shí)，進(jìn)行二分查找
	while(low <= high)
	{
		mid = (low + high) / 2; // 每次循環(huán)重新給mid賦值，改變中間值的下標(biāo)
		printf("low = %d, high = %d, mid = %d\n", low, high, mid); // 此處打印各個(gè)下標(biāo)值，方便觀測(cè)下標(biāo)變化
		// 如果中間值等于目標(biāo)值，說明查找成功，此時(shí)跳出循環(huán)
		if(a[mid] == target){
			printf("目標(biāo)值的下標(biāo)是%d\n", mid);
			break;
		}
		// 如果中間值大于目標(biāo)值，說明目標(biāo)值在左半邊，此時(shí)改變右邊界的下標(biāo)（縮減右半邊）
		if(a[mid] > target)
			high = mid - 1;
		// 如果中間值小于目標(biāo)值，說明目標(biāo)值在右半邊，此時(shí)改變左邊界的下標(biāo)（縮減左半邊）
		if(a[mid] < target)
			low = mid + 1;
	}
	
	// 當(dāng)左邊界已經(jīng)超過右邊界時(shí)，說明查找已經(jīng)結(jié)束
	if(low > high)
		printf("未找到目標(biāo)值\n");
	return 0;
}

注：以上代碼適用于數(shù)組已經(jīng)是升序排序的情況下。

運(yùn)行結(jié)果如下：

2.2 封裝函數(shù)（使用while循環(huán)）

使用while循環(huán)，將二分查找封裝成函數(shù)，代碼如下：

#include <stdio.h>

// 二分查找，找到元素返回索引值，否則返回-1
int binarySearch(int arr[], int len, int target) {
	int low = 0, high = len -1, mid; // 最小值、最大值和中間值的下標(biāo)
	while(low <= high) {
		mid = (low + high) / 2; // 每次循環(huán)重新給mid賦值，改變中間值的下標(biāo)
		if(arr[mid] == target) { // 如果中間值等于目標(biāo)值，說明查找成功，返回下標(biāo)
			return mid;
		} else if(arr[mid] > target) { // 如果中間值大于目標(biāo)值，說明目標(biāo)值在左半邊，此時(shí)縮減右半邊
			high = mid -1;
		} else { // 如果中間值小于目標(biāo)值，說明目標(biāo)值在右半邊，此時(shí)縮減左半邊
			low = mid + 1;
		}
	}
	return -1;
}

int main() {
	int a[] = {1, 5, 8, 11, 19, 22, 31, 35, 40, 49, 50}; 
	int len = sizeof(a) / sizeof(int);
	int index, target;
	printf("請(qǐng)輸入要查找的值：");
	scanf("%d", &target);
	index = binarySearch(a, len, target);
	printf("目標(biāo)值的下標(biāo)是%d\n", index);
	return 0;
}

運(yùn)行結(jié)果如下：

2.3 封裝函數(shù)（使用遞歸）

使用遞歸調(diào)用，將二分查找封裝成函數(shù)，代碼如下：

#include <stdio.h>

// 二分查找，找到元素返回索引值，否則返回-1
int binarySearch(int arr[], int low, int high, int target) {
	if(low <= high) {
		int mid = (low + high) / 2; // 每次遞歸重新給mid賦值，改變中間值的下標(biāo)
		if(arr[mid] == target) { // 如果中間值等于目標(biāo)值，說明查找成功，返回下標(biāo)
			return mid;
		} else if(arr[mid] > target) { // 如果中間值大于目標(biāo)值，說明目標(biāo)值在左半邊
			high = mid -1;
			return binarySearch(arr, low , high, target); // 繼續(xù)查找左半邊
		} else { // 如果中間值小于目標(biāo)值，說明目標(biāo)值在右半邊
			low = mid + 1;
			return binarySearch(arr, low , high, target); // 繼續(xù)查找右半邊
		}
	} else {
		return -1;
	}
}

int main() {
	int a[] = {1, 5, 8, 11, 19, 22, 31, 35, 40, 49, 50}; 
	int len = sizeof(a) / sizeof(int);
	int index, target;
	printf("請(qǐng)輸入要查找的值：");
	scanf("%d", &target);
	index = binarySearch(a, 0, len-1, target);
	printf("目標(biāo)值的下標(biāo)是%d\n", index);
	return 0;
}

注：使用遞歸查找，值得注意的是，每次遞歸時(shí)，需要縮小查找的范圍，也就是每次傳入的左右邊界發(fā)生了改變，因此入?yún)⒈赜?low 和 high，所以此處遞歸函數(shù)的定義是 binarySearch(int arr[], int low, int high, int target)，而不能像之前封裝while循環(huán)的函數(shù)定義 binarySearch(int arr[], int len, int target)文章來源地址http://www.zghlxwxcb.cn/news/detail-728620.html

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