【二分查找】

针对有序数组，性能非常好。

【时间复杂度】

logn

【代码】

#include <stdio.h>
#include <stdlib.h>

//非递归实现二分查找
int  BinarySearch1(int a[], int n, int key)
{
	int left, right;
	int mid;
	left = 0;
	right = n - 1;
	while(left <= right)
	{
		mid = (left + right) / 2;
		if(key == a[mid])
			return mid;
		else if(key > a[mid])
			left = mid + 1;
		else
			right = mid - 1;
	}
	return -1;
}

//递归实现二分查找
int BinarySearch2(int a[], int left, int right, int key)
{
	if(left > right)
		return -1;
	else
	{
		int mid = (left + right) / 2;
		if(key == a[mid])
			return mid;
		else if(key < a[mid])
			BinarySearch2(a, left, mid - 1, key);
		else
			BinarySearch2(a, mid + 1, right, key);
	}
}

int main(void)
{
	int a[13] = {3, 14, 27, 31, 39, 42, 55, 70, 74, 81, 85, 93, 98};
	int key = 81;
	int index1, index2;
	index1 = BinarySearch1(a, 13, key);
	index2 = BinarySearch2(a, 0, 13, key);
	printf("%d  %d\n", index1, index2);
	return 0;
}