Solutions to LeetCode 33 Search in Rotated Sorted Array.
LeetCode 33
Search in Rotated Sorted Array (Medium). [link]
- Iterative Binary Search. Time complexity O(log n). Space complexity O(1).
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
l, r = 0, len(nums)-1
if len(nums) == 0: return -1
while l < r:
m = l + (r - l) // 2
if nums[m] == target: return m
if nums[m] < nums[r]: # mid in right sorted half
if nums[r] < target or target < nums[m]: # target in left part
r = m
else:
l = m + 1
else: # mid in left sorted half
if nums[m] < target or target < nums[l]: # target in right part
l = m + 1
else:
r = m
return l if nums[l] == target else -1
- Recursive Binary Search. Time complexity O(log n). Space complexity O(1).
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
def binarySearch(nums, l, r, target):
if l > r : return -1
if len(nums) == 0: return -1
while l < r:
m = l + (r - l) // 2
if nums[m] == target: return m
if nums[m] < nums[r]: # mid in right sorted half
if nums[r] < target or target < nums[m]: # target in left part
return binarySearch(nums, l, m, target)
else:
return binarySearch(nums, m + 1, r, target)
else: # mid in left sorted half
if nums[m] < target or target < nums[l]: # target in right part
return binarySearch(nums, m + 1, r, target)
else:
return binarySearch(nums, l, m, target)
return l if nums[l] == target else -1
return binarySearch(nums, 0, len(nums)-1, target)
