C++之二分查找/折半查找（非递归和递归两种方式）

1、前提：

元素必须是有序的，若是无序，需要先进行排序。

2、基本思想：

假设元素表从小到大有序排列。用要查找的值x与中间节点的关键字比较，若相等，查找成功。若x小于中间节点的值，查找左表，若x大于中间节点的值，查找右表。这样递归进行，直到查找到或查找结束发现表中没有这样的节点。

3、复杂度分析：

最坏情况下，关键词比较次数为log2 (n+1)。所以，时间复杂度为O(log2 n).

4、代码及测试：

#include <iostream>
#include <assert.h>
using namespace std;

//二分查找非递归实现
template <class T> //使用模版函数，可以适用于不同类型：int 、float、double等
int BinarySearch(T a[], const T & x, int n) {
	int left = 0, right = n - 1;

	while(left <= right) { //注意这里不能丢掉＝，否则不能查找数组最后一个数
		int mid = (left + right)/2;
		if(a[mid] == x)
			return mid;
		if(a[mid] > x)
			right = mid - 1;
		else
			left = mid + 1;
	}
	return -1;
}
//二分查找递归实现
template<class T>
int BinarySearchRecursive(T a[], const T & x, int left, int right) {
	if(left > right) return -1;

	int mid = (left + right)/2;
	if(a[mid] == x) return mid;
	if(a[mid] > x) 
		return BinarySearchRecursive(a, x, left, mid - 1);
	else 
		return BinarySearchRecursive(a, x, mid + 1, right);
}

void test1() { //查找的值在数组第一个
	int a[] = {1,3,4,6,7,9};
	int x = 1;
	int len = sizeof(a)/sizeof(int);
	int find1 = BinarySearch(a, x, len);
	int find2 = BinarySearchRecursive(a, x, 0, len - 1);
	cout << find1 << endl;
	cout << find2 << endl;
 }

void test2() { //查找的值在数组中间
	int a[] = {1,3,4,6,7,9};
	int x = 4;
	int len = sizeof(a)/sizeof(int);
	int find1 = BinarySearch(a, x, len);
	int find2 = BinarySearchRecursive(a, x, 0, len - 1);
	cout << find1 << endl;
	cout << find2 << endl;
}

void test3() {  //查找的值在数组之后一位
	int a[] = {1,3,4,6,7,9};
	int x = 9;
	int len = sizeof(a)/sizeof(int);
	int find1 = BinarySearch(a, x, len);
	int find2 = BinarySearchRecursive(a, x, 0, len - 1);
	cout << find1 << endl;
	cout << find2 << endl;
}

void test4() { //查找的值不在数组中
	int a[] = {1,3,4,6,7,9};
	int x = 15;
	int len = sizeof(a)/sizeof(int);
	int find1 = BinarySearch(a, x, len);
	int find2 = BinarySearchRecursive(a, x, 0, len - 1);
	cout << find1 << endl;
	cout << find2 << endl;
}

int main() {

	test1();
	test2();
	test3();
	test4();
	return 0;
}