【设计和算法分析】3、二进制搜索

/**
* 书:《设计和算法分析》
* 特征:二进制搜索
*		1、建立a[0:n-1]是一排的阵列已经好序。请重写二进制搜索算法，因此，搜索元素时x不用时，该阵列。返回小于x最大的元素
*		S档I而超过x最小的元素位置j。在数组中的时候。I和j同样，均为x在数组中的位置
* 文件:lesson3.cpp
* 时间:2014年11月4日19:50:20
* 作者:cutter_point
*/

#include <iostream>

using namespace std;

//这里a是用来搜索的序列，n是序列里面数据的个数,x是要找的数，i和j是用来找位置的
bool erFen(int *a, int n, int x, int& i, int& j)	//i和j是两个引用
{
	int left = 0;	//查找的起始点
	int right = n - 1;	//查找的终点
	while (left < right)	//仅仅要还有数据没有被遍历,那就一直循环一直到找到，或者没有
	{
		int mid = (left + right) / 2;	//二分法的精髓，一分为二
		if (x == a[mid])	//从中间開始比較
		{
			i = j = mid;	//假设正好是中间的那个数的话,把位置赋值给i,j
			cout << "位置是：" << mid+1<<endl;
			return true;
		}
		//假设不是中间那个地方的话
		if (x > a[mid])	//因为是已经排好序了
		{
			//得到当前小于x的元素的位置
			j = mid;
			left = mid + 1;	//把后半部分作为新的起点
		}
		else
		{
			//得到当前大于x的元素位置
			i = mid;
			right = mid - 1;	//把前半部分作为新的数列
		}
	}

	//假设没有找到
	//i = right;
	//j = left;
	cout << "位置是：" << j+1 << " 和 " << i+1 << "之间" << endl;
	return false;
}

int main()
{
	int n, x, i=0, j=0;
	n = 0;
	cout << "依次输入数列的长度n,要找的整数x(中间用空格隔开)" << endl;
	cin >> n >> x;
	int *a;
	a = new int[n];
	cout << "输入数组数据：" << endl;
	for (int i = 0; i < n; ++i)
	{
		cin >> a[i];
	}

	erFen(a, n, x, i, j);	//i和j有两个引用

	getchar();
	return 0;
}