解析二分查找时间复杂度

话不多说，先来段二分查找的代码。

#define _CRT_SECURE_NO_WARNINGS 
#include<stdio.h>
int BinSearch(int arr[], int sz, int key){//找到返回下标，找不到返回-1
	int left = 0;
	int right = sz - 1;
	while (left <= right){
		int mid = left + ((right - left) >> 1);
		if (key < arr[mid]){
			right = mid - 1;
		}
		else if (key>arr[mid])
		{
			left = mid +1;
		}
		else
			return mid;
	}
	if (left > right)
		return -1;
}
int main()
{
	int arr[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	int sz = (sizeof(arr) / sizeof(arr[0]));
	int a = 1;
	int ret=BinSearch(arr, sz, a);
	printf("%d\n", ret);
	getchar();
	return 0;
}

首先，要求二分查找的时间复杂度就要知道什么是时间复杂度，时间复杂度其实就是一个函数，该函数计算的是执行基本能操作最坏的次数，在二分查找中，二分的次数就是基本语句的执行次数，我们不妨设次数为x,假设该数组的长度是n,一次二分后长度变为n/2,两次二分后长度变为n/4,........x次二分后长度变为n/(2)^x,假设最坏长度变为1才找到了key,此时可得(n/(2)^x)=1;可得x=log2n(log以2为底n的对数)，而在数据结构中常常这样写lgn,所以o()=o(lgn);