使用递归和非递归的方式实现二分查找

通过二分查找的方式来寻找整个有序数组中的指定值，主要思想是引入了一个mid变量，用下标为mid的值来和要查询的key比较，如果小于key就把查询的下限变换为mid+1，如果大于key就把查询的下限变换为mid-1，直到找到指定元素或下限大于上限或上限小于下限。递归的实现方式类似，循环的将上限、下限传递到函数中，函数的边界条件就是 下限大于上限或者找到指定元素！

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

int bs_unrecursive(int *a,int length, int key) {
	if (a == NULL)
		return -1;
	int low = 0;
	int high = length - 1;
	int mid = 0;
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (a[mid] < key)
			low = mid + 1;
		else if (a[mid] > key)
			high = mid - 1;
		else
			return mid;
	}
	return -1;
}

int bs_recursive(int *a,int low,int high, int key) {
	if (a == NULL)
		return -1;
	if (low > high)
		return -1;
	int mid = (low + high) / 2;
	if (a[mid] == key)
		return mid;
	else if (a[mid] < key)
		return bs_recursive(a, mid + 1, high, key);
	else
		return bs_recursive(a, low, mid - 1, key);
}
int main()
{
	int array[10];
	for (int i = 0; i < 10; i++)
		array[i] = i;
	int length = sizeof(array) / sizeof(array[0]);
	cout << "非递归实现:" << endl;
	cout << "元素下标:" << bs_unrecursive(array,length, 6) << endl;
	cout << "递归实现:" << endl;
	cout << "元素下标:" << bs_recursive(array, 0, 9, 6) << endl;
	return 0;
}

遗留问题：

• 如何跟踪递归深度？