FilesExpand file tree

 master

/

SearchInRotatedSortedArrayII81.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

217 lines (185 loc) · 6.68 KB

 master

/

SearchInRotatedSortedArrayII81.java

Copy path

Top

File metadata and controls

• Code
• Blame

217 lines (185 loc) · 6.68 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

205

206

207

208

209

210

211

212

213

214

215

216

217

/**

* Would this affect the run-time complexity? How and why?

*

* 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).

*

* Write a function to determine if a given target is in the array.

*

* The array may contain duplicates.

*

* Follow up for "Search in Rotated Sorted Array":

* What if duplicates are allowed?

*/

public class SearchInRotatedSortedArrayII81 {

public boolean search(int[] nums, int target) {

System.out.println(Arrays.toString(nums));

int L = nums.length;

if (L == 0) return false;

int mid = L/2;

if (nums[mid] == target) {

return true;

}

return (search(Arrays.copyOfRange(nums, 0, mid), target) ||

search(Arrays.copyOfRange(nums, mid+1, L), target));

}

// now, let's truncate it, and do not use array copy

// public boolean search(int[] nums, int target) {

// int L = nums.length;

// if (L == 0) return false;

//

// if (nums[0] < nums[L-1] && (nums[0] > target || nums[L-1] < target)) {

// return false;

// }

//

// if (nums[0] > nums[L-1] && target < nums[0] && nums[L-1] < target) {

// return false;

// }

//

// int mid = L/2;

// if (nums[mid] == target) {

// return true;

// }

//

// return (search(Arrays.copyOfRange(nums, 0, mid), target) ||

// search(Arrays.copyOfRange(nums, mid+1, L), target));

// }

//now, let's truncate it, and do not use array copy

public boolean search2(int[] nums, int target) {

int L = nums.length;

if (L == 0) return false;

return searchHelper(nums, target, 0, L-1);

}

private boolean searchHelper(int[] nums, int target, int s, int e) {

if (s > e) return false;

int mid = (e-s)/2 + s;

if (nums[mid] == target) {

return true;

}

if (nums[s] < nums[e] && (nums[s] > target || nums[e] < target)) {

return false;

}

if (nums[s] > nums[e] && target < nums[s] && nums[e] < target) {

return false;

}

return (searchHelper(nums, target, s, mid-1) || searchHelper(nums, target, mid+1, e));

}

/**

* https://discuss.leetcode.com/topic/25487/neat-java-solution-using-binary-search

*/

public boolean search3(int[] nums, int target) {

int start = 0, end = nums.length - 1;

//check each num so we will check start == end

//We always get a sorted part and a half part

//we can check sorted part to decide where to go next

while(start <= end){

int mid = start + (end - start)/2;

if(nums[mid] == target) return true;

//if left part is sorted

if(nums[start] < nums[mid]){

if(target < nums[start] || target > nums[mid]){

//target is in rotated part

start = mid + 1;

}else{

end = mid - 1;

}

}else if(nums[start] > nums[mid]){

//right part is sorted

//target is in rotated part

if(target < nums[mid] || target > nums[end]){

end = mid -1;

}else{

start = mid + 1;

}

}else{

//duplicates, we know nums[mid] != target, so nums[start] != target

//based on current information, we can only move left pointer to skip one cell

//thus in the worest case, we would have target: 2, and array like 11111111, then

//the running time would be O(n)

start ++;

}

}

return false;

}

public boolean search4(int[] nums, int target) {

int L = nums.length;

if (L == 0) return false;

return searchHelper2(nums, target, 0, L-1);

}

private boolean searchHelper2(int[] nums, int target, int s, int e) {

if (s > e) return false;

int mid = (e+s)/2;

if (nums[mid] == target) {

return true;

}

if (nums[s] < nums[mid]) {

if (target >= nums[s] && target <= nums[mid]) {

return searchHelper2(nums, target, s, mid-1);

} else {

return searchHelper2(nums, target, mid+1, e);

}

} else if (nums[s] > nums[mid]) {

if (target >= nums[mid] && target <= nums[e]) {

return searchHelper2(nums, target, mid+1, e);

} else {

return searchHelper2(nums, target, s, mid-1);

}

} else {

return searchHelper2(nums, target, s+1, e);

}

}

/**

* https://leetcode.com/problems/search-in-rotated-sorted-array-ii/discuss/28212/When-there-are-duplicates-the-worst-case-is-O(n).-Could-we-do-better

*/

public boolean search5(int A[], int key) {

int l = 0, r = A.length - 1;

while (l <= r) {

int m = l + (r - l)/2;

if (A[m] == key) return true; //return m in Search in Rotated Array I

if (A[l] < A[m]) { //left half is sorted

if (A[l] <= key && key < A[m])

r = m - 1;

else

l = m + 1;

} else if (A[l] > A[m]) { //right half is sorted

if (A[m] < key && key <= A[r])

l = m + 1;

else

r = m - 1;

} else l++;

}

return false;

}

public boolean search6(int[] nums, int target) {

if (nums == null || nums.length == 0) return false;

int start = 0;

int end = nums.length - 1;

while (start < end) {

int mid = start + (end - start) / 2;

int midVal = nums[mid];

if (midVal == target) return true;

if (midVal > nums[start]) {

if (target >= nums[start] && target < midVal) {

end = mid -1;

} else {

start = mid + 1;

}

} else if (midVal < nums[end]) {

if (target > midVal && target <= nums[end]) {

start = mid + 1;

} else {

end= mid - 1;

}

} else {

if (midVal == nums[start]) {

start++;

}

if (midVal == nums[end]) {

end--;

}

}

}

return nums[start] == target;

}

}