[LeetCode] 33. Search in Rotated Sorted Array

轉自LeetCode

Suppose a sorted array 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.

<Solution>

這題是要在 rotate 過的 sorted list 裡面找值，且 rotate 的位置不知道

因為可能有 rotate 過，所以會有一個區段就不是 sorted 了

那因為題目有說，list 裡面不會有重複的值，這個讓難度有降低

思考的情況有幾種

• 如果沒有 rotate 過，第一個元素一定小於最後一個元素，因為是 sorted list，反之則有rotate過

• 如果沒有 rotate 過，那 target < 第一個元素，或是 target > 最後一個元素，就返回 -1，因為一定不在 list 裡

• 如果有 rotate 過，那 target < 第一個元素且 target > 最後一個元素，就返回 -1，因為一定不在 list 裡

• 如果上述情況都不符合，就要開始找

• 沒有 rotated，可以歷遍找，也可以用 binary search 找，都會過，用 binary search 會快一點

• 有 rotated，先看 target 是在左半還是右半，大於等於第一個元素，在左半，反之在右半

• 在左半，從第一個元素找起，遇到下一個元素比目前小，代表找不到了

• 在右半，從最後一個元素找起，遇到下一個元素比目前大，代表找不到了

code 如下


也可以直接用 binary search 來找

kotlin