一、題目
假設按照升序排序的數(shù)組在預先未知的某個點上進行了旋轉擅腰。
( 例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )歼争。
搜索一個給定的目標值渗勘，如果數(shù)組中存在這個目標值，則返回它的索引乔遮，否則返回 -1 价淌。
你可以假設數(shù)組中不存在重復的元素。
你的算法時間復雜度必須是 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
二病毡、解題
1、先創(chuàng)建兩個指針left和right，然后取mid=(right+left)/2,將數(shù)組一分為二淌喻。其中肯定有一個有序雀摘，一個可能有序或者部分有序，
2阵赠、然后在有序的范圍內判斷target是否在有序范圍內，然后移動left或right匕荸，繼續(xù)步驟一枷邪，直到找到nums[mid] == target,返回mid，否則返回-1践惑。
詳細步驟見代碼救斑。
時間復雜度：O(log(n))×澈颍空間復雜度：O(1)。
三泵额、代碼實現(xiàn)
class Solution {
func search(_ nums: [Int], _ target: Int) -> Int {
var left = 0
var right = nums.count - 1
while left <= right {
// 當前居中的位置
let mid = (right + left) / 2
if nums[mid] == target {// 循環(huán)執(zhí)行,知道找到nums[mid] == target,然后返回mid
return mid
}
// 如果nums[mid] < nums[right]說明,mid->right是有序的
if nums[mid] < nums[right] {
// 如果target在nums[mid]與nums[right]之間,left向右移動至mid+1
if nums[mid] < target && target <= nums[right] {
left = mid + 1
}else {// 否則right向左移動至mid-1
right = mid - 1
}
}else{// 否則說明left->mid是有序的
// 如果target在nums[left]與nums[right]之間,right向左移動至mid-1
if nums[left] <= target && target < nums[mid] {
right = mid - 1
}else{// 否則left向左移動至mid+1
left = mid + 1
}
}
}
return -1
}
}
Demo地址：github
