Search in rotated sorted array
[Leetcode][Arrays]
Problem Statement
Suppose an array sorted in ascending order 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. URL
Your algorithm's runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1Example 3:
Input: nums = [4,5,6,7,0,1,2], target = 1
Output: 5#collapse-hide
from typing import List
class Solution:
def search(self, nums: List[int], target: int) -> int:
l = 0
r = len(nums)-1
if len(nums) == 0:
return -1
if len(nums) == 1:
if target == nums[0]:
return 0
else:
return -1
if nums[len(nums)//2] == target:
return len(nums)//2
while(l != r and len(nums) > l and len(nums) > r):
if nums[l] == target:
return l
if nums[r] == target:
return r
l += 1
r -= 1
return -1
sol = Solution()
sol.search([1, 3, 5, 6, 9, 2], 19)
