@@ -22,53 +22,113 @@ class Solution(object):
2222 def search (self , nums , target ):
2323 if not nums or len (nums )== 0 :
2424 return - 1
25-
25+
2626 l = 0
2727 r = len (nums )- 1
2828 while True :
2929 m = (l + r )/ 2
30-
30+
3131 left_num = nums [l ]
3232 right_num = nums [r ]
3333 mid_num = nums [m ]
34-
34+
3535 if left_num == target :
3636 return l
3737 if right_num == target :
3838 return r
3939 if mid_num == target :
4040 return m
41-
41+
4242 #break the array into two part
4343 #l~m and m~r
44-
44+
4545 if left_num < target and target < mid_num :
4646 #l~m is sorted and target is inside
4747 #do the same calculation to this part
4848 r = m - 1
4949 continue
50-
50+
5151 if mid_num < target and target < right_num :
5252 #m~r is sorted and target is inside
5353 #do the same calculation to this part
5454 l = m + 1
5555 continue
56-
56+
5757 #if the code goes here
5858 #the target doesn't exist or
5959 #one of two part is not sorted
6060 #the target is in the not sorted part
61-
61+
6262 if mid_num > right_num :
6363 #m~r is not sorted
6464 #check m+1~r
6565 l = m + 1
6666 continue
67-
67+
6868 if mid_num < left_num :
6969 #l~m is not sorted
7070 #check l~m-1
7171 r = m - 1
7272 continue
7373
7474 return - 1
75+
76+
77+ """
78+ If we slice (anywhere) in the rotated-sorted-array, there must be one part already sorted, another part still rotated.
79+ If the right most elemant in the array is greater than the left most (`nums[l]<nums[r]`), then it is **sorted**.
80+ If the array is sorted, we can apply binary search in it.
81+
82+ So for every part of the array, we first determine if it is sorted.
83+ If it is sorted apply binary search.
84+ If it is not sorted, check if the target in the sorted part. If not, search the other part.
85+ """
86+ class Solution (object ):
87+ def search (self , nums , target ):
88+ if nums is None or len (nums )== 0 : return - 1
89+
90+ l = 0
91+ r = len (nums )- 1
92+
93+ while l <= r :
94+ p = (l + r )/ 2
95+
96+ if nums [l ]== target : return l
97+ if nums [p ]== target : return p
98+ if nums [r ]== target : return r
99+
100+ #array sorted
101+ if nums [l ]< nums [r ]:
102+ #binary search
103+
104+ #check target is in range
105+ if target < nums [l ] or nums [r ]< target :
106+ return - 1
107+
108+ if target < nums [p ]:
109+ r = p - 1
110+ else :
111+ l = p + 1
112+
113+ #array not sorted
114+ else :
115+ #the left half is sorted
116+ if nums [l ]< nums [p ]:
117+ #the left half is sorted and target in it, search left.
118+ if nums [l ]< target and target < nums [p ]:
119+ r = p - 1
120+ else :
121+ l = p + 1
122+
123+ #the right half is sorted
124+ else :
125+ #the right half is sorted and target in it, search right.
126+ if nums [p ]< target and target < nums [r ]:
127+ l = p + 1
128+ else :
129+ r = p - 1
130+ return - 1
131+
132+
133+
134+
0 commit comments