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

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

二分查找的思想：

 二分查找就是在一個有序的一維數(shù)組中找到想要找到的那個數(shù)key。先給出一個有序的一維數(shù)組，并表明想要找到的數(shù)，然后定義兩個指針，一個指向數(shù)組的首地址left，一個指向數(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("無此數(shù)\n");
	}
	else
	{
		printf("%d",ret);
	}
	return 0;
}

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