~二分查找~

       二分查找本应是一个特别简单的算法，不就是在一个有序的数组中每次取其下标的中间值，与所找的元素对比。若是相等则返回该值；若是不相等则重新确定下标区间，再取其下标的中间值，与所找的元素对比，如此反复查找即可。

       按照这种思想，我们可以运用一个循环语句即可完成算法，代码如下：

int BinarySearch(int* a, size_t n, int x)
{
	assert(a);

	int left = 0;
	int right = n;

	while(left < right)
	{
		int mid = left + ((right - left)>>1);

		if(a[mid] > x)
		{
			right = mid - 1;
		}
		else if(a[mid] < x)
		{
			left = mid + 1;
		}
		else
		{
			return mid;
		}
	}
	return -1;
}

int main()
{
	int arr[] = {0,1,2,3,4,5,6,7,8,9};

	for(size_t i=0; i<11; ++i)
	{
		cout<<BinarySearch(arr, 10, i)<<" ";
	}

	cout<<endl;

	system("pause");
	return 0;
}

       可，运算结果却是：

似乎与想要的结果有些差异，这又是为什么呢？看来，二分法也并非想象中的那般简单！！！

严格说来，二分查找的关键在于left、right的取值范围：

1.非递归算法

1) 若left、right的取值范围为 [0，n）

       因取值范围的右边是非法位置，故left应小于 right，若给出left <= right，则访问到非法位置，发生越界；

       正确的代码如下：

int BinarySearch(int* a, size_t n, int x)
{
	assert(a);

	int left = 0;
	int right = n;

	while(left < right)
	{
		int mid = left + ((right - left)>>1);

		if(a[mid] > x)
		{
			right = mid;
		}
		else if(a[mid] < x)
		{
			left = mid + 1;
		}
		else
		{
			return mid;
		}
	}
	return -1;
}

2) left、right的取值范围是[0，n-1]

       因取值范围的右边是合法位置，故left应小于等于right，若给出left < right，则未访问到某些位置，造成结果出错（死循环）；

       正确的代码如下：

int BinarySearch(int* a, size_t n, int x)
{
	assert(a);

	int left = 0;
	int right = n - 1;

	while(left <= right)
	{
		int mid = left + ((right - left)>>1);

		if(a[mid] > x)
		{
			right = mid - 1;
    		}
 		else if(a[mid] < x)
		{
			left = mid + 1;
		}
		else
		{
			return mid;
		}
	}
	return -1;
}

2.递归算法

       递归算法中所考虑的细节与非递归算法相同，可参照上述所写内容。

       代码如下：

int BinarySearch(int* a, int left, int right, int x)
{
	assert(a);

	if(left <= right)
	{
		int mid = left + ((right - left)>>1);

		if(a[mid] < x)
		{
			return BinarySearch(a, mid+1, right, x);
		}
		else if(a[mid] > x)
		{
			return BinarySearch(a, left, mid-1, x);
		}
		else
		{
			return mid;
		}
	}
	return -1;
}

3.测试用例

int main()
{
	int arr[] = {0,1,2,3,4,5,6,7,8,9};

	//非递归算法的测试用例
	cout<<BinarySearch(arr, 10, 0)<<endl;
	cout<<BinarySearch(arr, 10, 1)<<endl;
	cout<<BinarySearch(arr, 10, 2)<<endl;
	cout<<BinarySearch(arr, 10, 3)<<endl;
	cout<<BinarySearch(arr, 10, 4)<<endl;
	cout<<BinarySearch(arr, 10, 5)<<endl;
	cout<<BinarySearch(arr, 10, 6)<<endl;
	cout<<BinarySearch(arr, 10, 7)<<endl;
	cout<<BinarySearch(arr, 10, 8)<<endl;
	cout<<BinarySearch(arr, 10, 9)<<endl;
	cout<<BinarySearch(arr, 10, 10)<<endl;

	//递归算法的测试用例
	cout<<BinarySearch(arr, 0, 9, 0)<<endl;
	cout<<BinarySearch(arr, 0, 9, 1)<<endl;
	cout<<BinarySearch(arr, 0, 9, 2)<<endl;
	cout<<BinarySearch(arr, 0, 9, 3)<<endl;
	cout<<BinarySearch(arr, 0, 9, 4)<<endl;
	cout<<BinarySearch(arr, 0, 9, 5)<<endl;
	cout<<BinarySearch(arr, 0, 9, 6)<<endl;
	cout<<BinarySearch(arr, 0, 9, 7)<<endl;
	cout<<BinarySearch(arr, 0, 9, 8)<<endl;
	cout<<BinarySearch(arr, 0, 9, 9)<<endl;
	cout<<BinarySearch(arr, 0, 9, 10)<<endl;

	system("pause");
	return 0;
}