Leetcode/1-100q/33.py at master · Garvit244/Leetcode · GitHub

Name: Leetcode/1-100q/33.py at master · Garvit244/Leetcode · GitHub
Rating: 4.4 (9757 reviews)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
'''
 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.

 Your algorithm's runtime complexity must be in the order of O(log n).
'''

classSolution(object):
defsearch(self, nums, target):
"""
 :type nums: List[int]
 :type target: int
 :rtype: int
 """
ifnotnums:
return-1

left, right=0, len(nums) -1

whileleft<=right:
mid= (left+right) /2
ifnums[mid] ==target:
returnmid

ifnums[left] <=nums[mid]:
iftarget>=nums[left] andtarget<=nums[mid]:
right=mid-1
else:
left=mid+1
else:
iftarget>=nums[mid] andtarget<=nums[right]:
left=mid+1
else:
right=mid-1

return-1


classSolution(object):
defsearch(self, nums, target):
"""
 :type nums: List[int]
 :type target: int
 :rtype: int
 """

defsearchRecursive(nums, left, right, target):
ifleft>right:
return-1

mid= (left+right) /2
ifnums[mid] ==target:
returnmid

ifnums[left] <=nums[mid]:
ifnums[left] <=target<nums[mid]:
returnsearchRecursive(nums, left, mid-1, target)
else:
returnsearchRecursive(nums, mid+1, right, target)
else:
ifnums[mid] <target<=nums[right]:
returnsearchRecursive(nums, mid+1, right, target)
else:
returnsearchRecursive(nums, left, mid-1, target)

returnsearchRecursive(nums, 0, len(nums)-1, target)