牛客 小米 旋转数组中的最小元素 二分

题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。
输入描述:

一个排好序的数组的一个旋转
数组长度不超过1000000

输出描述:

该数组的最小值

示例1
输入
复制

3 4 5 1 2

输出
复制

1

看到有序,一般可以想到二分,因为有序有单调性
把图像画出来如下

二分

• 当中点高于右端点,说明中点可以向右偏移一点

•  while(lef < rig) {
   	mid = (lef + rig) >> 1;
   	if(a[mid] > a[rig]) lef = mid + 1;
   	else if(a[mid] < a[rig]) rig = mid;
   	else rig = rig - 1;
   }
   printf("%d\n", a[rig]);