C++将一个有序数组按顺序移动，在移动后的数组中查找一个数字

在有序数组中查找一个数字，可以使用二分查找
该题给定的是有序数组移动后的数组，所以不能直接利用二分查找
给定的数组为
4, 5, 6, 7, 8, 9, 1, 2, 3

思路是先找到断点，也就是该数组中数字1所在的位置
由于数组是一个升序排列的有序数组，所以我们同样可以利用二分的思路去查找断点

		if (src[mid] > src[mid + 1])
		{
			return mid + 1;
		}

此时断点的位置就是 mid + 1

		else if (src[left] > src[mid])
		{
			right = mid - 1;
		}

此时断点的位置在 mid 的左边（按照升序的思路左边的值应该比右边的小）

		else
		{
			left = mid + 1;
		}

排除了前两种情况， 断点应该在mid的右边

寻找断点的函数实现如下：

int findBreakPoints(const vector<int> & src){
	int left = 0;
	int right = src.size() - 1;
	int mid;

	while (left <= right)
	{
		mid = (left + right) / 2;
		
		if (src[mid] > src[mid + 1])
		{
			return mid + 1;
		}

		else if (src[left] > src[mid])
		{
			right = mid - 1;
		}
		else
		{
			left = mid + 1;
		}
	}
	return 0;
}

完整代码如下：

#include <iostream>
#include <vector>

using namespace std;

//比如原有序数组为[ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
//左移三次后变为[ 4, 5, 6, 7, 8, 9, 1, 2, 3 ]

int findBreakPoints(const vector<int> & src){
	int left = 0;
	int right = src.size() - 1;
	int mid;

	while (left <= right)
	{
		mid = (left + right) / 2;
		
		if (src[mid] > src[mid + 1])
		{
			return mid + 1;
		}

		else if (src[left] > src[mid])
		{
			right = mid - 1;
		}
		else
		{
			left = mid + 1;
		}
	}
	return 0;
}

int findNumber(const vector<int> & src, int bp, int to_find)
{
	int left = bp;
	int size = src.size();
	int right = bp + size - 1;
	int mid;

	while (left <= right)
	{
		mid = (left + right) / 2;

		if (src[mid % size] > to_find)
		{
			right = mid - 1;
		}

		else if (src[mid % size] < to_find)
		{
			left = mid + 1;
		}

		else
		{
			return mid % size;
		}
	}
	return 0;
}

int main()
{
	vector<int> src{ 4, 5, 6, 7, 8, 9, 1, 2, 3 };

	int bp = findBreakPoints(src);

	cout << findNumber(src, bp, 6) << endl;

	system("pause");
	return 0;
}