forked from rpj911/LeetCode_algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSearchInRotatedSortedArray2.java
More file actions
204 lines (177 loc) · 5.61 KB
/
SearchInRotatedSortedArray2.java
File metadata and controls
204 lines (177 loc) · 5.61 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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
package Algorithms.array;
/*
* https://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/
*
* Search in Rotated Sorted Array II Total Accepted: 18427 Total Submissions: 59728 My Submissions
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
* */
public class SearchInRotatedSortedArray2 {
/*
In this function, the complex may go to O(n). It depents on how many duplicates exit in the array.
if there are M duplicates, the complexity may be O(logN + M).
*/
public boolean search(int[] A, int target) {
if (A == null || A.length == 0) {
return false;
}
// setup two point to the left and right of the array.
int l = 0, r = A.length - 1;
while (l <= r) {
// get the mid point.
int mid = l + (r - l)/2;
if (target == A[mid]) {
return true;
}
if (A[mid] > A[l]) {
// the left side is sorted.
if (target <= A[mid] && target >= A[l]) {
// target is in the left side.
r = mid - 1;
} else {
l = mid + 1;
}
} else if (A[mid] < A[l]) {
// the right side is sorted.
if (target <= A[r] && target >= A[mid]) {
// target is in the right side.
l = mid + 1;
} else {
r = mid - 1;
}
} else {
// when A[mid] == A[l], we can't determin, just move the
// left point one
l++;
}
}
return false;
}
/*
* 2015.1.1 Redo:
* */
public boolean search1(int[] A, int target) {
if (A == null || A.length == 0) {
return false;
}
int l = 0;
int r = A.length - 1;
while (l < r - 1) {
int mid = l + (r - l) / 2;
if (A[mid] == target) {
return true;
}
// left sort
if (A[mid] > A[l]) {
// out of range.
if (target > A[mid] || target < A[l]) {
l = mid + 1;
} else {
r = mid - 1;
}
// right sort.
} else if (A[mid] < A[l]) {
// out of range.
if (target < A[mid] || target > A[r]) {
r = mid - 1;
} else {
l = mid + 1;
}
} else {
// move one node.
l++;
}
}
if (A[l] == target || A[r] == target) {
return true;
}
return false;
}
// Version 2:
public boolean search2(int[] A, int target) {
if (A == null || A.length == 0) {
return false;
}
int l = 0;
int r = A.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (A[mid] == target) {
return true;
}
// left sort
if (A[mid] > A[l]) {
// out of range.
if (target > A[mid] || target < A[l]) {
l = mid + 1;
} else {
r = mid - 1;
}
// right sort.
} else if (A[mid] < A[l]) {
// out of range.
if (target < A[mid] || target > A[r]) {
r = mid - 1;
} else {
l = mid + 1;
}
} else {
// move one node.
l++;
}
}
return false;
}
// Version3: Drop the sides quicker.
public boolean search3(int[] A, int target) {
if (A == null) {
return false;
}
int l = 0;
int r = A.length - 1;
while (l < r - 1) {
int mid = l + (r - l) / 2;
int value = A[mid];
if (target == value) {
return true;
}
// The right side is sorted.
if (value < A[l]) {
if (target > A[r] || target < value) {
// Drop the right side.
r = mid;
} else {
// Drop the left side.
l = mid;
}
// The left side is sorted.
} else if (value > A[l]){
if (target > value || target < A[l]) {
// drop the left side.
l = mid;
} else {
r = mid;
}
} else {
if (value > A[r]) {
// The right side is unordered, so the left side should be ordered.
if (target > value || target < A[l]) {
// drop the left side.
l = mid;
} else {
r = mid;
}
}
l++;
}
}
if (A[l] == target) {
return true;
} else if (A[r] == target) {
return true;
}
return false;
}
}