leetcode 33. Search in Rotated Sorted Array
程序员文章站
2022-07-16 11:52:55
...
In order to help me understand all the possible situations I should consider, I just draw a picture to make everything easier.
So acutally there are four situations we should consider, we should first see where middle pointer points at, and then consider whether target is in the left part or right part
class Solution(object):
def search(self, nums, target):
start = 0
end = len(nums) - 1
while start <= end:
middle = (start + end) // 2
if nums[middle] == target: # if we find target
return middle
if nums[middle] > nums[end]: # in situation 1
if target >= nums[start] and target < nums[middle]: # target in left part in situtation 1
if target == nums[start]: return start
end = middle - 1
else: # target in right part in situation 1
start = middle + 1
if start >= len(nums):
return -1
else:# in situation 2
if target >= nums[middle] and target <= nums[end]: # target in right part in situation 2
if target == nums[end]: return end
start = middle + 1
else: # target in left part in situation 2
end = middle - 1
if end < 0:
return -1
return -1
上一篇: 最大子矩阵和
下一篇: LintCode题目:字符串中的单词数
推荐阅读
-
【LeetCode】Two Sum & Two Sum II - Input array is sorted & Two Sum IV - Input is a BST
-
Convert Sorted Array to Binary Search Tree
-
【一天一道LeetCode】#26. Remove Duplicates from Sorted Array
-
LeetCode 33. Search in Rotated Sorted Array && 81. Search in Rotated Sorted Array II
-
Leetcode 33 Search in Rotated Sorted Array
-
LeetCode·33. Search in Rotated Sorted Array
-
leetcode 33. Search in Rotated Sorted Array
-
0033_Search in Rotated Sorted Array
-
Search in Rotated Sorted Array II
-
33. Search in Rotated Sorted Array