剑指 Offer 11. 旋转数组的最小数字

题目链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/

本文采用JavaScript语言解题：一、暴力法　　二、递归二分法

一、暴力法

这次所使用的暴力法还蛮欣赏的，紧抓数组的结构性质进行暴力解决

 1 /**
 2  * @param {number[]} numbers
 3  * @return {number}
 4  * 根据数组元素的构造规则，
 5  * 只要遇到比第一个元素小的数，这个数就是数组最小数字，否则第一个元素就是最小数字
 6  */
 7 var minArray = function(numbers) {
 8     if(numbers == null) return numbers;
 9     let length = numbers.length;
10     let pre = numbers[0];
11     for(let i = 1; i < length; i++) {
12         if(numbers[i] < pre) return numbers[i];
13     }
14     return pre;
15 };

 二、递归二分法

“暴力是解决不了问题的”（我们都是斯文人，hh~）

重要的思想收获：

使用二分法去查找数据，其中的数据不一定非得有序；我们只需有能力（数据的存放方式让你有这个能力）知道要查找的东西在这边还是在那边。

 1 /**
 2  * @param {number[]} numbers
 3  * @return {number}
 4  * 二分搜索
 5  * 判断最小值在左半部分还是在右半部
 6  */
 7 var minArray = function (numbers, left = 0, right = numbers.length - 1) {
 8   if (left == right) return numbers[left];
 9   let mid = Math.trunc(left + (right - left) / 2);
10   // 解决存在重复数的情况，消去重复数（消去重复数并不会影响结果，因为被消去的重复数最终还是会剩下一个）
11   while (mid < right && numbers[mid] == numbers[right]) right--;
12   while (mid > left && numbers[mid] == numbers[left]) left++;
13   if (numbers[mid] > numbers[right]) return minArray(numbers, mid + 1, right);
14   //左半部分非升序时，mid可能为最小值（参数right = mid而不是right = mid - 1）
15   else return minArray(numbers, left, mid); 
16 };