題目

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).

假設(shè)一個(gè)升序的數(shù)組，在數(shù)組中任意一個(gè)位置旋轉(zhuǎn)后，在這個(gè)旋轉(zhuǎn)后的數(shù)組中找出給定目標(biāo)值target的位置，如果不存在返回-1

• Example1

[0,1,2,4,5,6,7]--旋轉(zhuǎn)后--[4,5,6,7,0,1,2],target=0
所以返回0所在位置 4

• Example2

[0,1,2,4,5,6,7]--旋轉(zhuǎn)后--[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
  // 右邊數(shù)組，是有序的
   }else if(nums[mid] < nums[right] ){
 // 目標(biāo)值在右邊，繼續(xù)二分遍歷
      if(nums[mid] < target && target <= nums[right]) left = mid + 1
  // 目標(biāo)值在左邊，繼續(xù)二分遍歷
      else right = mid -1
   }else{// 這里說(shuō)明左邊是有序的
// 目標(biāo)值在左邊，繼續(xù)二分遍歷
      if(nums[mid] > target && nums[left] <= target) right = mid - 1
/ 目標(biāo)值不在左邊，那么肯定在右邊，繼續(xù)二分遍歷
      else left = mid + 1
   }
 }
// 遍歷完沒(méi)有目標(biāo)值返回-1
 return  -1

}

• 題目分析

* 此題目關(guān)鍵在于，中間值如果小于數(shù)組最右邊的那個(gè)值，那么說(shuō)明右半部分?jǐn)?shù)組是有序的
nuns[mid] < nums[length - 1] // 右邊部分?jǐn)?shù)組有序
nuns[mid] > nums[length - 1] // 左邊部分?jǐn)?shù)組有序