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
146 lines (127 loc) · 4.01 KB
/
SearchInRotatedSortedArray2.java
File metadata and controls
146 lines (127 loc) · 4.01 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
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;
}
}