题目：
难度：Middle
相关话题：数组、二分查找
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是O (logn ) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1
思路：
二分，首先要找到旋转点；
找旋转点：选择一个随机位置mid，如果这个位置比nums[0]大，那么说明旋转点还在右边； 如果这个位置比nums[0]更小，说明旋转点就是当前点或者在当前点的左边。
找出旋转点后，整个数组就被分割成了旋转点以左和旋转点以右，这两边都是有序的。
找target点：判断target在左侧还是在右侧，接着用最基本的二分查找target。
/**
* @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
if(nums.length===0)return -1
let rotateIdx=findPivot(nums)
if(target>=nums[0] && target<=nums[rotateIdx-1]){
return bs(nums,0,rotateIdx-1)
}else{
return bs(nums,rotateIdx,nums.length-1)
}
function findPivot(arr){
let lo=0,hi=arr.length-1
while(lo<hi){
let mid=Math.floor((lo+hi)/2)
if(arr[mid]>=arr[0]) lo=mid+1
else hi=mid
}
return lo
}
function bs(nums,lo,hi){
while(lo<=hi){
let mid=Math.floor((lo+hi)/2)
if(nums[mid]>target) hi=mid-1
else if(nums[mid]<target)lo=mid+1
else return mid
}
return -1
}
};