旋转数组的最小数字(改造二分法)

题目

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

思路

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

• 以分割点作为边界，数组总是被分为有序和无序两部分，最小值总是在无序的这一边的，所以每次切割后都要将范围缩减到无序这一侧
  比如上面的{4,5,1,2,3} 以一分为二后以1作为边界的话分为：{1,2,3}有序，{4,5,1}无序

• 二分切割到最后剩下两个元素时，发现最小值总是在右边
  比如上面的{4,5,1} 以一分为二后以1作为边界的话分为：{4,5}有序，{5,1}无序,结果总是左边是最大值，右边是最小值

代码实现

• 取中间值 mid=(begin+end)/2 ,写为 begin+((end-begin)>>1) 更高效
• 判断无序侧并缩减的方法：arr[mid]>=arr[begin]时，是左侧有序，应该使 begin=mid 否则是右侧有序，应该使end=mid
• while 循环直至剩下两个元素，即循环条件为 while(begin+1 < end)
• 循环结束，剩下两个元素时，arr[end]即为最小的元素，arr[begin] 即为最大的元素

function minNum ($arr) {
    $begin = 0;
    $end = count($arr) - 1;

    //考虑没有旋转这种特殊的旋转（1,2,3,4,5）
    if ($arr[$begin] < $arr[$end]) {
        return $arr[$begin];
    }

    //begin和end指向相邻元素，退出
    //while 循环直至剩下两个元素，即循环条件为 while(begin+1 < end)
    while ($begin+1 < $end) {
        $mid = $begin + (($end-$begin)>>1);//等价于($begin+$end)/2，更高效 
        //要么数组的左侧有序，要么右侧有序
        if ($arr[$mid]>=$arr[$begin]) {//左侧有序 
           $begin = $mid;
        } else {
           $end = $mid;
        }
    }
    return $arr[$end];
}

echo minNum(array(5,1,2,3,4));
结果 ： 1