https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。你可以假设数组中不存在重复元素。
输入: [3,4,5,1,2]
输出: 1
输入: [4,5,6,7,0,1,2]
输出: 0
-
二分法
-
假设
var arr = [a, b, c, d, e, f, g, h, i, j ,k]为初始数组，则必有k > a，当数组在元素 e 发生旋转，旋转为var reversedArr = [e, f, g, h, i, j ,k, a, b, c, d]则必有d < e -
若数组
arr[arr.length - 1] > arr[0]则数组未旋转过 -
若
arr[arr.length - 1] < arr[0]则发生过旋转 -
对于旋转过的数组，利用二分法进行大小比较，设初始最小元素为
arr[0]，设数组中位数为arr[mid] -
若
arr[0] > arr[mid]则说明mid位置的元素应该在arr[0]元素之前，那么在左半区继续查找，并同时设置min = arr[mid] -
右半区类似查找
- 旋转之后 [0] 索引的位置一定是旋转点，利用旋转点进行查找