[leetcode] No 33. Search in Rotated Sorted Array Python
[Problem]
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= 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,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
[Explanation]
In this problem, there is a target and an array. In this array, I have to find targeted value's location in O(lon n) time.
It means that not all arrays can be searched. If using for N state, time limitation will be happened.
[Solution]
In this problem, Binary Search is useful!
Binary search is a method of searching for the wanted answer by dividing an array in half continuously.
In my solution, the median index is the dividing criterion.
After dividing based a median index, I search right side and left side each several times until finding the targeted value.
| class Solution: def Find(self, START, END, nums, target): if START > END: return -1 MID = int((END + START)/2) ans = -1 if target == nums[MID]: return MID if target == nums[END]: return END if target == nums[START]: return START if nums[MID] > nums[END]: ans = self.Find(MID+1, END-1, nums, target) if nums[MID] < nums[START]: ans = self.Find(START+1, MID-1, nums, target) if nums[MID] < target < nums[END]: ans = self.Find(MID+1, END-1, nums, target) if nums[START] < target < nums[MID]: ans = self.Find(START+1, MID-1, nums, target) if ans != -1: return ans return ans def search(self, nums: List[int], target: int) -> int: start = 0 end = len(nums) - 1 result = self.Find(start, end, nums, target) return result |
