// 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
// 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。
// 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
// NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
// Solution:https://www.cnblogs.com/edisonchou/p/4746561.html
// - 隐藏条件1:旋转之后的数组实际上可以划分为两个非递减的子数组(记为list-1和list2)
// - 而且list-1的元素都大于或者等于list-2的元素。
// - 隐藏条件2:最小的元素刚好是这两个子数组的分界线。
// - 隐藏条件3:arr[0]及其之后的若干个元素可能等于arr[length-1],可以在二分前先移动start
function minNumberInRotateArray(arr) {
// write code here
if(arr === null || arr.length === 0)
return 0;
let start = 0;
let end = arr.length - 1;
// 一旦发现数组中第一个数字小于最后一个数字,表明该数组是排序的
// 就可以直接返回第一个数字了
let mid = start;
while(arr[start] >= arr[end]) {
// 退出循环条件
if(end - start === 1) {
mid = end;
break;
}
mid = Math.floor((start+end)/2);
// 特殊情况:如果下标为start、end和mid指向的三个数字相等,则只能顺序查找
if(arr[start] === arr[mid] && arr[mid] === arr[end]) {
let min = arr[start];
for(let i=start+1; i<=end; i++) {
if(arr[i] < min)
min = arr[i];
}
return min;
}
// 缩小范围
if(arr[mid] >= arr[start]) // mid在list-1
start = mid;
else if(arr[mid] <= arr[end]) // mid在list-2
end = mid;
}
return arr[mid];
}
// test -------------------------------
let arr = [3, 4, 5, 1, 1, 2];
console.log(minNumberInRotateArray(arr));