C語言折半查詢法的由來及使用詳解

2022-08-18 14:02:47

引入二分查詢

本文帶著大家學習一個簡單的**二分查詢演演算法，也叫折半查詢演演算法**

先給大家提出一個問題

額，大家應該都會碰到這種情況，那大家怎麼猜呢？

我想一定是會說1000，他說太少了，你又猜1500…

這其實就是二分查詢的應用。

接下來我們來看一個問題

如何在一個有序陣列中查詢一個數位？

有一部分帥氣的觀眾可能會說:

直接遍歷陣列，一個一個對比就找到了啊

但是大家有沒有想過一個問題，陣列中如果只有幾十個數的話，那完全可以這樣做

那如果陣列中有幾十萬個呢？

這樣遍歷絕對是非常消耗時間，題目很明確說有序陣列，如果直接遍歷，我們是不是對不起有序這二字呢？

分析二分查詢

我們用一個簡單的範例來實現一下二分查詢

比如有這樣一個陣列

計算中間下標的兩種方法

我們在其中查詢一個數位。使用二分查詢，我們如何確定中間值呢？

有人說，陣列長度除以二，但是中間值會變，陣列長度不可變 ----排除

這邊我們給大家帶來兩種方法來計算中間值

首先大家要清楚，我們要有兩個邊界，就是範圍，比如鞋子02000變成10002000

我們使用兩個下標作為兩端，left 以及 right 中間值我們定義為mid

第一種

mid = (left + right) / 2;

我對長度為奇數和偶數的陣列都進行了分析，這種方法並沒有漏過任何一個數，所以可以使用

第二種

第一種方法有一種弊病，如果陣列特別長的話，left+right可能會超出型別的最大值範圍

我們得想辦法解決掉這個問題

假如我們把left最上邊那一小塊放到left上邊，是不是就是中間值了呢

、

把這種方法寫成表示式就是

mid = (right - left) / 2 + left;

這就是兩種計算中間下標的方法

程式碼實現

當mid處的值 < 待查詢的值的時候，需要把 mid處的以及前邊的捨棄,即left右移， left = mid +1;
當mid處的值 > 待查詢的值的時候，需要把 mid處的以及後邊的捨棄,即right左移，right = mid -1;
當相等時，便不再查詢。

還有一個問題,什麼時候就不再查詢了呢？

left < right 時，中間仍有資料未查詢
left = right 時，有一個數未比較
left>right 時，都找完了，沒找到

所以當left > right 時，就沒必要查詢了

話不多說，直接上程式碼

#include <stdio.h>
//詳解二分查詢
int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	//計算陣列長度
	int length = sizeof(arr) / sizeof(arr[0]);
	int n = 0;//待查詢的值
	scanf("%d", &n);
	int left = 0;//左下標
	int right = length - 1;//右下標
	int mid = 0;//中間下標
	while(left <= right)
	{
		mid = (left + right) / 2;
		if(arr[mid] > n)
		{
			right = mid - 1;
		}
		else if (arr[mid] < n)
		{
			left = mid + 1;
		}
		else
		{
			printf("找到了，下標為%dn", mid);
			break;
		}
	}
	if (left > right)
	{
		printf("找不到，陣列中不存在該值n");
	}
	return 0;
}