C++ 笔试基础题 23 循环有序数组最小值练习题 6.3

链接：https://www./courses/1/6/4
来源：牛客网

对于一个有序循环数组arr，返回arr中的最小值。有序循环数组是指，有序数组左边任意长度的部分放到右边去，右边的部分拿到左边来。比如数组[1,2,3,3,4]，是有序循环数组，[4,1,2,3,3]也是。

给定数组arr及它的大小n，请返回最小值。

测试样例：

[4,1,2,3,3],5

返回：1

若不满足条件：即arr[L]>=arr[R],表明发生了数组，循环。

  
 发生此种情况：表示在L和M之间，有最小值：

 
  发生此种情况：表示在M和R之间，有最小值：

 
 若发生此种情况：一一遍历，寻找最小值。

链接：https://www./courses/1/6/4
来源：牛客网

class MinValue {
public:
	int getMin(vector<int> arr, int n) {
		if (n == 0){
			return -1;
		}
		int left = 0;
		int right = n - 1;
		if (arr[left] < arr[right]){
			return arr[left];
		}
		while (left <= right){
			if (left == right - 1){
				return arr[left] < arr[right] ? arr[left] : arr[right];
			}
			int mid = left + (right - left) / 2;
			if (arr[left] > arr[mid]){
				right = mid;
			}else if (arr[mid] < arr[right]){
				left = mid;
			}
			else{
				break;
			}
		}
		int min = INT_MAX;
		for (int i = 0; i < arr.size(); i++){
			if (arr[i] < min){
				min = arr[i];
			}
		}
		return min;
	}
};