153. 寻找旋转排序数组中的最小值

输入: [3,4,5,1,2]
输出: 1

输入: [4,5,6,7,0,1,2]
输出: 0

 比较次数 o(n)
 执行用时: 28 ms, 在Find Minimum in Rotated Sorted Array的C++提交中击败了2.89% 的用户

/**
   Time  complexity:T(n) = O(1) + T(n/2) = O(logn)
   Space complexity:o(1)
   查找逻辑跟索引位置切分的，根数据大小没关系，数据全部相等，也没有关系
   **/
   int find_min(vector<int>&nums,int start,int end){     
       if((end-start)<=1)
       {       return min(nums[start],nums[end]);    
       }        
       if (nums[end]>nums[start])
        {            
          return nums[start];
       }        
         int mid=(start+end)/2;        
        int left=find_min(nums,start,mid);       
        int right=find_min(nums,mid+1,end);        
        return min(left,right);   }   
    

/** 第一题 find-minimum-in-rotated-sorted-array
https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/description/
153. 寻找旋转排序数组中的最小值
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
请找出其中最小的元素。期望:请找出其中最小的元素
拦路虎：
1. 如果是完全升序  第一数字就是 ，
  旋转数值是升序（相邻的元素都是递增）， 根本不知道抄那个方向移动？炸锅了。
  肯定没有那么容易赛。
2. 我想通过观察特点 怪点(2边元素都大于它)就是最小元素这个没问题，，需要至少4个元素判断 很容易越界。 i++。i--都比较复杂了
  还是回到问题1，
比较点【相邻元素】【边界元素】【变化点】都有缺陷
过程描述
随便寻找一个数字i,判断nums[i]是否为最小值
1 如果nums[i]>nums[end]，说明nums[i]不是最小元素 ，最小元素在后面 ---> i+1
2.如哦nums[i]<nums[end],nums[end]不是最小元素，后面元素比当前元素i还大，这是升序 最小元素在前面  <---- i-1
 但是最后一个元素情况下 nums[end]可能是最小元素 i（这个)
3 如果 nums[i]==nums[end] 相等的话就舍去一个呀（这个遗漏了）
4 折半查找直到循环结束，范围缩小到最后一个元素 （这个不是一般能想到的，讨巧了，时候才知道，不是通用的方法 if 判断 watch结果是否越界）测试：
1 int{1, 2, 3, 4, 5, 6} 如果升序不需要排序 上面规则不在查找了 ok
2 {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}  ok
3.{3, 3, 1, 3} 完全错误的是
缺点：
1. 通过数字的大小有关系,
跟数字的内容有关系，需要很复杂的逻辑判断。 有点不是很好
find-minimum-in-rotated-sorted-array-ii case3的时候我代码完全不对了
2. 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 性能o(n)case1 寻找不到怎么办
别人的答案：
https://www.youtube.com/watch?v=P4r7mF1Jd50&t=3s
http://zxi.mytechroad.com/blog/divide-and-conquer/leetcode-153-find-minimum-in-rotated-sorted-array/
！！！！！！！！！
折半查找没有问题，但是元素比较出现了问题，无论怎么比较都不对，比较元素这个思路是错误的**/func findMin(nums []int) int {
   begin := 0
   end := len(nums) - 1
   mid := 0
   if nums[end] > nums[begin] {        //fmt.Println("sort array", nums[begin])
       return nums[begin]
   }    for begin < end {
       mid = (begin + end) / 2
       if nums[end] < nums[mid] {
           begin = mid + 1 //排除nums[mid]不是最小元素,最小元素在后面
       } else if nums[end] > nums[mid] {
           end = mid
       } else {
           end--
       }        //fmt.Println(begin, end, mid)
   }    return nums[begin]}