二分法改造灵活运用

二分法改造灵活运用 学习目标：

熟练掌握二分法精髓

---

题目：

旋转数组 改造二分法 （加深理解）
给定一个递增数组的旋转，把最开始的几个数移动到后面，用二分法查找最小值

---

思路：

其实这道题用正常的查找方法很简单，看看自己能不能用二分法求解呢？

首先给定一个数组，把前面的n项移动到数组的后面

例如：{1，2，3,4,5,6}的一个旋转是{4,5,6,1,2,3}。

不难发现，如果把数组分为有序部分，和无序部分，那么最小值1一定是在无序部分，且无论怎样旋转，他的前一位一定是最大的那个。

那么只有两种情况：（1）有序的部分在mid的左边

                                （2）有序的部分在mid的右边

代码如下

 if(arr[mid]>arr[low]){
 	low=mid;
 }else if(arr[mid]

这里定义low为起点，mid中只，high是终点；

如果发现arr[mid]>arr[low]说明无序的部分在右边，那把查找的区域往后推，low=mid；

如果发现arr[mid]

加上二分法迭代写法的循环条件：

for(mid;mid>low;mid=low+(high-low>>1))
{
 if(arr[mid]>arr[low]){
 	low=mid;
 }else if(arr[mid]

就搞定啦！

---

代码：

//旋转数组 改造二分法 （加深理解）
//给定一个递增数组的旋转，把最开始的几个数移动到后面，用二分法查找最小值
#include
#include
using namespace std;
int main()
{
int arr[]={7,8,9,1,2,3,4,5,6}; 
int len=sizeof(arr)/sizeof(arr[0])-1;
int mid=len/2;
int high=len-1;
int low=0;
for(mid;mid>low;mid=low+(high-low>>1))
{
 if(arr[mid]>arr[low]){
 	low=mid;
 }else if(arr[mid]