Chapter2: 时间复杂度分析、递归、查找与排序

10. 解题实战：旋转数组中的最小数字(改造二分法)

题目

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

算法

显然要利用题目的有序性来提升算法性能，自然而然地就想到二分法

原理

观察反转数组特点：{3,4,5,1,2}、{4，5，1，2，3}、{5，6，1，2，3，4}等，将其一分为二，发现

• 包括分割点作为边界，数组总是被分为有序和无序两部分，最小值总是在无序的这一边的，所以每次切割后都要将范围缩减到无序这一侧

  比如上面的{3,4,5}有序，{5,1,2}无序

• 二分切割到最后剩下两个元素时，发现最小值总是在右边

  比如上面第一个示例最后剩下{5,1},结果总是左边是最大值，右边是最小值

代码实现

• 取中间序号即mid=(begin+end)/2 ,写为 begin+((end-begin)>>1) 更高效

• 判断无序侧并缩减的方法：

  • arr[mid]>=arr[begin] 时，是左侧有序，应该使 begin=mid (注意对于[0,1,1,1,1]这类有重复的数组这种判断方法不灵)
  • 否则是右侧有序，应该使end=mid
  • while 循环直至剩下两个元素，即循环条件为 while(begin+1 < end)

• 循环结束，剩下两个元素时，arr[end]即为最小的元素，arr[begin] 即为最大的元素

代码

/*找反转数组中最小的数
反转数组：将递增数组前面的一部分数保持顺序放到数组尾部
如{3,4,5,1,2} 、{4,5,1,2,3} 
*/
int min(int* arr,int arrLen){
   int begin=0;
   int end=arrLen-1;
   while(begin+1<end){
       int mid=begin+((end-begin)>>1);//等价于(begin+end)/2，更高效 
       //要么数组的左侧有序，要么右侧有序
       if(arr[mid]>=arr[begin]){//左侧有序 
           begin=mid; 
       } else{
           end=mid;
       }
   }
   return arr[end];
}