不了解Binary Search演算法,可以參考[演算法筆記] Binary Search文章
Problem
題號:Leetcode 33
標題:Search in Rotated Sorted Array
演算法:Binary Search
Explain
1.找ASC排序區段:mid值 > left值
2. 斷判Target值是不是在ASC區段
- 是:Target在ASC區段,Target >= left && Target < Mid
移動right指標:right = mid — 1
- 不是:Target在mid另一半段
移動left指標:left = mid + 1
3. 終止迴圈條件:
a. 找到Targe
b. left > right
Solution
class Solution {
func search(_ nums: [Int], _ target: Int) -> Int {
var left = 0
var right = nums.count - 1
while left <= right {
let mid = (left+right)/2
if nums[mid] == target {
return mid
}
if nums[mid] >= nums[left] {
//左半部是由小到大,包括mid
if target >= nums[left], target < nums[mid] {
//targe在左半部
right = mid - 1
} else {
left = mid + 1
}
} else {
//右半部是由小到大,包括mid
if target <= nums[right], target > nums[mid] {
//target在右半部
left = mid + 1
} else {
right = mid - 1
}
}
}
return -1
}
}