[LeetCode] 81 | Search in Rotated Sorted Array II | Python

---

문제 링크: https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

---

문제

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

---

조건

• 1 <= nums.length <= 5000
• $-10^4$ <= nums[i] <= $10^4$
• nums is guaranteed to be rotated at some pivot.
• $-10^4$ <= target <= $10^4$

---

내 풀이

주어진 nums 리스트를 차례로 보면서 nums[n]==target이면 True를 리턴한다.

nums에 target이 없다면 nums[n-1] < target < nums[n]이 성립하기 때문에 False를 리턴해준다.

nums[n-1] < target < nums[n]가 성립하지 않으면서 nums에 target이 없는 경우(ex. [3,4,0,1], target=2)에는 for문이 끝날 때까지 리턴되지 않을 것이므로 for문이 끝난 후에 False를 리턴한다.

---

코드

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        if nums[0] == target:   return True
        
        for n in range(1, len(nums)):
            if nums[n] == target:
                return True
            elif nums[n-1] < target < nums[n]:
                return False
        
        return False