【算法专栏】旋转数组的最小数字（原创）
本系列是《剑指offer》或leetcode的JavaScript版本。 每期1-2个算法，也有可能是一个类别。 文章包括题目、思路以及代码。 如果您对本期有不同或者更好的见解，请后台留言，喜欢请点个好看，谢谢阅读。
题目1-用两个栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。
基本思路
栈1:
用于入队列存储
栈2:
出队列时将栈1的数据依次出栈，并入栈到栈2中
栈2出栈即栈1的底部数据即队列要出的数据。
注意:
栈2为空才能补充栈1的数据，否则会打乱当前的顺序。
代码
const stack1 = [];const stack2 = [];
function push(node){ stack1.push(node);}function pop(){ if(stack2.length === 0){ while(stack1.length>0){ stack2.push(stack1.pop()); } } return stack2.pop() || null;}题目2-旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
基本思路
肯定不能直接遍历，失去了这道题的意义
旋转数组其实是由两个有序数组拼接而成的，因此我们可以使用二分法，只需要找到拼接点即可。
(1)array[mid] > array[high]:
出现这种情况的array类似[3,4,5,6,0,1,2]，此时最小数字一定在mid的右边。low = mid + 1
(2)array[mid] == array[high]:
出现这种情况的array类似 [1,0,1,1,1] 或者[1,1,1,0,1]，此时最小数字不好判断在mid左边 还是右边,这时只好一个一个试 。high = high - 1
(3)array[mid] < array[high]:
出现这种情况的array类似[2,2,3,4,5,6,6],此时最小数字一定就是array[mid]或者在mid的左 边。因为右边必然都是递增的。high = mid
代码
function minNumberInRotateArray(arr){ let len = arr.length; if(len == 0) return 0; let low = 0, high = len - 1; while(low < high) { let mid = low + Math.floor((high-low)/2); if(arr[mid] > arr[high]) { low = mid + 1; } else if(arr[mid] == arr[high]) { high = high - 1; } else { high = mid; } }
return arr[low];}扩展
二分查找
function binarySearch(data, arr, start, end) { if (start > end) { return -1; } var mid = Math.floor((end + start) / 2); if (data == arr[mid]) { return mid; } else if (data < arr[mid]) { return binarySearch(data, arr, start, mid - 1); } else { return binarySearch(data, arr, mid + 1, end); } }腾讯云开发者
