假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個點上進行了旋轉(zhuǎn)菌羽。
( 例如纷闺，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )。
搜索一個給定的目標值犁功，如果數(shù)組中存在這個目標值，則返回它的索引浸卦，否則返回 -1 。
你可以假設(shè)數(shù)組中不存在重復(fù)的元素限嫌。
你的算法時間復(fù)雜度必須是 O(log n) 級別。
示例 1:
輸入: nums = [4,5,6,7,0,1,2], target = 0
輸出: 4
示例 2:
輸入: nums = [4,5,6,7,0,1,2], target = 3
輸出: -1
AC代碼
class Solution {
public int search(int[] nums, int target) {
if(nums == null || nums.length == 0) {
return -1;
}
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] == target) {
return mid;
}
if(nums[mid] > nums[right]) {
//left ordered
if(target >= nums[left] && target < nums[mid]) {
right = mid - 1;
}else {
left = mid + 1;
}
}else {
//right ordered
if(target > nums[mid] && target <= nums[right]) {
left = mid + 1;
}else {
right = mid - 1;
}
}
}
return -1;
}
}
一遍AC 哈哈哈
精髓
lgn復(fù)雜度炉抒，必須二分查找稚叹，原始的二分的判斷條件就是拿中間的值與兩邊對比，本題是變形塞茅。中間值大于右邊值說明左邊有序，判斷target是不是在左區(qū)間內(nèi)野瘦，不是的話就查找右區(qū)間飒泻，是就查找左區(qū)間；中間值小于右邊說明右邊有序泞遗，類似判斷target可能在哪個區(qū)間內(nèi)
