二分查找及其時(shí)間復(fù)雜度

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

金州網(wǎng)站建設(shè)公司創(chuàng)新互聯(lián)公司,金州網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為金州1000+提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\外貿(mào)營(yíng)銷(xiāo)網(wǎng)站建設(shè)要多少錢(qián)，請(qǐng)找那個(gè)售后服務(wù)好的金州做網(wǎng)站的公司定做！

二分查找的思想：

 二分查找就是在一個(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 <stdio.h>

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("無(wú)此數(shù)\n");
	}
	else
	{
		printf("%d",ret);
	}
	return 0;
}

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

本文題目：二分查找及其時(shí)間復(fù)雜度
路徑分享：http://muchs.cn/article20/pidejo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信小程序、商城網(wǎng)站、做網(wǎng)站、動(dòng)態(tài)網(wǎng)站、電子商務(wù)、企業(yè)建站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)