二分查找又稱折半查找，它是一種效率較高的查找方法。

班戈ssl適用于網(wǎng)站、小程序/APP、API接口等需要進(jìn)行數(shù)據(jù)傳輸應(yīng)用場(chǎng)景，ssl證書未來市場(chǎng)廣闊！成為創(chuàng)新互聯(lián)建站的ssl證書銷售渠道，可以享受市場(chǎng)價(jià)格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：028-86922220（備注：SSL證書合作）期待與您的合作！

二分查找的思想：

 二分查找就是在一個(gè)有序的一維數(shù)組中找到想要找到的那個(gè)數(shù)key。先給出一個(gè)有序的一維數(shù)組，并表明想要找到的數(shù)，然后定義兩個(gè)指針，一個(gè)指向數(shù)組的首地址left，一個(gè)指向數(shù)組的最后right，求出數(shù)組中間的下標(biāo)mid=(left+right)/2，以mid為劃分，如果key=arr[mid];找到了結(jié)束，如果key>arr[mid];

在arr[mid]+1到right中間找，并且將left指向arr[mid]+1，繼續(xù)在left和right中間根據(jù)折半的方法查找，直到找到key結(jié)束。如果arr[mid]>key,在left和arr[mid]+1中間找，并且將right指向arr[mid]+1;

繼續(xù)在left和right中間根據(jù)折半的方法查，直到找到結(jié)束。

#include 

int binsearch(int a[],int num, int len)
{
	int left = 0;
	int right = len-1;
	while(left <= right)
	{
		int mid = (left + right)/2;
		if (a[mid] == num)
		{
			return num;
		}
		else if(a[mid] > num)
		{
			right = mid-1;
		}
		else
		{
			left = mid + 1;
		}
	}
	return -1;
}

int main()
{
	int arr[] = {1,2,3,4,5,6,7,8,9};
	int key = 9;
    int sz = sizeof(arr)/sizeof(arr[0]);
	int ret = binsearch(arr,key,sz);
	if (ret == -1)
	{
		printf("無此數(shù)\n");
	}
	else
	{
		printf("%d",ret);
	}
	return 0;
}

時(shí)間復(fù)雜度為O(lgN);二分查找第一次分為兩部分，第二次分為四部分，第三次八部分.....相當(dāng)為一顆二叉樹。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

網(wǎng)站標(biāo)題：二分查找及其時(shí)間復(fù)雜度-創(chuàng)新互聯(lián)
文章出自：http://weahome.cn/article/dojeoc.html