[解題筆記] Leetcode#33 — Search in Rotated Sorted Array

Photo by Chris Ried on Unsplash

不了解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
    }
}