题目

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm's runtime complexity must be in the order of O(log n).

假设一个升序的数组，在数组中任意一个位置旋转后，在这个旋转后的数组中找出给定目标值target的位置，如果不存在返回-1

• Example1

[0,1,2,4,5,6,7]--旋转后--[4,5,6,7,0,1,2],target=0
所以返回0所在位置 4

• Example2

[0,1,2,4,5,6,7]--旋转后--[4,5,6,7,0,1,2],target=3
以返回0所在位置 3

• 解法

let left = 0;
 let right = nums.length - 1
 while(left <= right){
   let mid = Math.floor( (left + right) /2 )
   if(nums[mid] === target) {
     return mid
  // 右边数组，是有序的
   }else if(nums[mid] < nums[right] ){
 // 目标值在右边，继续二分遍历
      if(nums[mid] < target && target <= nums[right]) left = mid + 1
  // 目标值在左边，继续二分遍历
      else right = mid -1
   }else{// 这里说明左边是有序的
// 目标值在左边，继续二分遍历
      if(nums[mid] > target && nums[left] <= target) right = mid - 1
/ 目标值不在左边，那么肯定在右边，继续二分遍历
      else left = mid + 1
   }
 }
// 遍历完没有目标值返回-1
 return  -1

}

• 题目分析

* 此题目关键在于，中间值如果小于数组最右边的那个值，那么说明右半部分数组是有序的
nuns[mid] < nums[length - 1] // 右边部分数组有序
nuns[mid] > nums[length - 1] // 左边部分数组有序