題目
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ù)組有序
