学步园

题目来自剑指offer

题目：

思路：

根据指针low，mid，high三个指针指向元素的大小确定二分往左走还是往右走

如果arr[low] <= arr[mid]：则区间[low,mid]的元素是递增的，有升有降应该在右边区间，应该往右走

如果arr[low] > arr[mid]：  则区间[low,mid]的元素是有递增有递减，则应该往左走

终止条件：

区间只剩两个元素时，终止。此时该区间肯定值一个大一个小（high指向），此时返回high指向元素即可

注意：

有一种情况解决不了。

在arr[low] = arr[mid] = arr[high]时，此时无法确定之后处理左区间还是右区间。此时只能对该区间直接顺序遍历找到最小数

举例：

当数组元素为 1 0 1 1 1 和 1 1 1 0 1，上述思路无法同时处理这两种情况。

即上述思路，要求low，mid，high三个指针指向的三个元素至少有一个元素是不同的。

代码：

不完全正确的代码：

int BinSearch(int nArr[],int nStart,int nEnd)
{
	assert(nArr != NULL && nStart >= 0 && nEnd >= nStart);
	int nLow = nStart;
	int nHigh = nEnd;
	int nMid = -1;
	while (nLow + 1 < nHigh)
	{
		nMid = (nLow + nHigh)/2;
		if (nArr[nLow] <= nArr[nMid])//向右走
		{
			nLow = nMid;
		}
		else //向右走
		{
			nHigh = nMid;
		}
	}
	//终止时，有指针nLow和nHigh相邻，指向的两个元素肯定是一升一降，nLow指向大元素，nHigh指向小元素
	assert(nHigh >= nStart && nHigh <= nEnd);
	return nArr[nHigh];
}

正确代码：

int BinSearch(int nArr[],int nStart,int nEnd)
{
	assert(nArr != NULL && nStart >= 0 && nEnd >= nStart);
	int nLow = nStart;
	int nHigh = nEnd;
	int nMid = -1;
	while (nLow + 1 < nHigh)
	{
		nMid = (nLow + nHigh)/2;
		if (nArr[nLow] == nArr[nMid] && nArr[nMid] == nArr[nHigh])
		{
			//不能区分往左走还是往右走，此时要顺序查找
			int nMin = 0x3f3f3f3f;
			for (int i = nLow;i <= nHigh;i++)
			{
				if (nMin > nArr[i])
				{
					nMin = nArr[i];
				}
			}
			return nMin;
		}
		if (nArr[nLow] <= nArr[nMid])//向右走
		{
			nLow = nMid;
		}
		else //向右走
		{
			nHigh = nMid;
		}
	}
	//终止时，有指针nLow和nHigh相邻，指向的两个元素肯定是一升一降，nLow指向大元素，nHigh指向小元素
	assert(nHigh >= nStart && nHigh <= nEnd);
	return nArr[nHigh];
}

测试代码：

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

int BinSearch(int nArr[],int nStart,int nEnd)
{
	assert(nArr != NULL && nStart >= 0 && nEnd >= nStart);
	int nLow = nStart;
	int nHigh = nEnd;
	int nMid = -1;
	while (nLow + 1 < nHigh)
	{
		nMid = (nLow + nHigh)/2;
		if (nArr[nLow] == nArr[nMid] && nArr[nMid] == nArr[nHigh])
		{
			//不能区分往左走还是往右走，此时要顺序查找
			int nMin = 0x3f3f3f3f;
			for (int i = nLow;i <= nHigh;i++)
			{
				if (nMin > nArr[i])
				{
					nMin = nArr[i];
				}
			}
			return nMin;
		}
		if (nArr[nLow] <= nArr[nMid])//向右走
		{
			nLow = nMid;
		}
		else //向右走
		{
			nHigh = nMid;
		}
	}
	//终止时，有指针nLow和nHigh相邻，指向的两个元素肯定是一升一降，nLow指向大元素，nHigh指向小元素
	assert(nHigh >= nStart && nHigh <= nEnd);
	return nArr[nHigh];
}

int main()
{
	//int nArr[5] = {3,4,5,1,2};
	//int nArr[5] = {3,1,2,3,4};
	//int nArr[5] = {3,1,1,1,1};
	//int nArr[5] = {3,3,3,3,1};
	//int nArr[5] = {1,1,1,1,1};
	//int nArr[5] = {1,0,1,1,1};
	int nArr[5] = {1,1,1,0,1};
	cout<<BinSearch(nArr,0,4)<<endl;
	system("pause");
	return 1;
}