这是letcode上的一道题目 Leetcode: Find Minimum in Rotated Sorted Array
一、什么是旋转数组呢，就是一个有序的数组，在从某一个位置开始，旋转到数组的另一端，例如：0
1 2 3 4 5 6 -> 4 5 6 0 1 2 3
二、使用暴力的方式就是遍历这个数组，算法的复杂度就是O（N），但是根据一般的经验提到有序，就会考虑到使用二分将算法的复杂度降低到O(logn)，当然这个题目也不例外，但是如何利用二分去求解呢，毕竟不是全部有序。
首先我们先找到数组的中点在慢慢的分析，设左右边界和中点分别是left,right,mid，旋转数组有个特性也是必然，那就是中点分成的两段数组必然有一段是有序的，而另一端有可能还是旋转数组或是有序的数组，例如4
5 6 0 1 2 3中点分开的两边都是有序数组，3
4 5 6 1 2中点分开的左边是有序的，右边还是旋转数组。根据这个特性我们有以下的分析。
1、如何中点分开的数组左边有序a[left]
<= a[mid]
（1）同时右边也是有序的，a[mid]
<= a[right]，那么a[left]就是最小值
（2）如果中点到右边界是无序的 a[mid] > a[right]，那么left = mid -1去右边寻找最小值
2、如果 a[left] > a[mid] 左端是无序的
（1）同时a[mid] < a[right] 那么就需要继续二分，但是不减1（因为mid有可能就是波谷）
（2）同时a[mid] > a[right] 这种情况不可能发生，因为这种情况会导致整体反序，与旋转数组不符
代码如下：
#include <stdio.h>
int find_min(int* arr, int l, int h)
{
if(arr == NULL)
return -1;
if(l > h)
return -1;
int mid;
while(l < h)
{
mid = l + (l + h) >> 1;
if(arr[l] <= arr[mid]) //左侧有序
{
if(arr[mid] <= arr[h]) //右侧也有序
{
return l;
}
else
{
l = mid + 1;
}
}
else //右侧有序 左侧有可能有波谷
{
h = mid;
}
}
return l;
}
int main(int argc, char *argv[])
{
int a1[] = {4, 5 ,6 ,1 ,2 ,3};
int a2[] = {1, 2, 3, 4, 5, 6};
int a3[] = {2, 1};
int a4[] = {1};
int a5[] = {3, 1, 2};
printf("%d\n", find_min(a1, 0, 5));
printf("%d\n", find_min(a2, 0, 5));
printf("%d\n", find_min(a3, 0, 1));
printf("%d\n", find_min(a4, 0, 0));
printf("%d\n", find_min(a5, 0, 2));
}
结果是：
3
0
1
0
1