forked from wuduhren/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsearch-in-rotated-sorted-array.py
More file actions
74 lines (60 loc) · 2.21 KB
/
search-in-rotated-sorted-array.py
File metadata and controls
74 lines (60 loc) · 2.21 KB
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
72
73
74
#https://leetcode.com/problems/search-in-rotated-sorted-array/
#we break the nums into two part
#we assume they are sorted
#so in each part, if the target is inside, it will meet
#left_most_number <= target <= right_most_number
#if the target is inside the part
#we do the same calculation to that smaller part
#if we can't find target in both part
#one of two part is not sorted, and the target is inside the not sorted one
#why can we be sure only one part is not sorted?
#because the original array is sorted and just done once rotation
#so we check if it is sorted
#if it is not sorted
#we do the same calculation to that smaller part
#the part will become smaller and smaller exponentially
#so it is O(logN)
class Solution(object):
def search(self, nums, target):
if not nums or len(nums)==0:
return -1
l = 0
r = len(nums)-1
while True:
m = (l+r)/2
left_num = nums[l]
right_num = nums[r]
mid_num = nums[m]
if left_num==target:
return l
if right_num==target:
return r
if mid_num==target:
return m
#break the array into two part
#l~m and m~r
if left_num<target and target<mid_num:
#l~m is sorted and target is inside
#do the same calculation to this part
r = m-1
continue
if mid_num<target and target<right_num:
#m~r is sorted and target is inside
#do the same calculation to this part
l = m+1
continue
#if the code goes here
#the target doesn't exist or
#one of two part is not sorted
#the target is in the not sorted part
if mid_num>right_num:
#m~r is not sorted
#check m+1~r
l = m+1
continue
if mid_num<left_num:
#l~m is not sorted
#check l~m-1
r = m-1
continue
return -1