-
Notifications
You must be signed in to change notification settings - Fork 1
/
LeetCode-33-Search-in-Rotated-Sorted-Array.java
130 lines (113 loc) · 4.78 KB
/
LeetCode-33-Search-in-Rotated-Sorted-Array.java
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
/*
LeetCode: https://leetcode.com/problems/search-in-rotated-sorted-array/
LintCode: http://www.lintcode.com/problem/search-in-rotated-sorted-array/
JiuZhang: http://www.jiuzhang.com/solutions/search-in-rotated-sorted-array/
ProgramCreek: http://www.programcreek.com/2014/06/leetcode-search-in-rotated-sorted-array-java/
Analysis:
*/
class Solution {
// 1.Iterative(Similar to JiuZhang's solution)
// This kind of search will never let lo and hi to be overlapped, so need additional check the value of lo and hi in the end
// public int search(int[] nums, int target) {
// if (nums == null || nums.length == 0) return -1;
// int lo = 0, hi = nums.length - 1;
// while (lo + 1 < hi) {
// int mid = lo + (hi - lo) / 2;
// if (nums[mid] == target) {
// return mid;
// }
// if (nums[mid] >= nums[0]) {
// // means mid is in the left side of pivot
// if (nums[lo] <= target && target < nums[mid]) {
// // means target is between lo and mid
// hi = mid;
// } else {
// lo = mid;
// }
// } else {
// // means mid is in the right side of pivot
// if (nums[mid] < target && target <= nums[hi]) {
// // means target is between mid and hi
// lo = mid;
// } else {
// hi = mid;
// }
// }
// }
// if (nums[lo] == target) return lo;
// if (nums[hi] == target) return hi;
// return -1;
// }
// 2.Iterative (make the lo and hi could overlap)
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) return -1;
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return mid;
// Be careful that mid could be equal to 0 (the lower boundary) when there are only two elements.
if (nums[mid] >= nums[0]) {
// means mid is in the left side of pivot
if (nums[lo] <= target && target < nums[mid]) {
// means target is between lo and mid
hi = mid - 1;
} else {
lo = mid + 1;
}
} else {
// means mid is in the right side of pivot
if (nums[mid] < target && target <= nums[hi]) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
return - 1;
}
// 3.Recursive
// public int search(int[] nums, int target) {
// if (nums == null || nums.length == 0) return -1;
// return search(nums, target, 0, nums.length - 1);
// }
// private int search(int[] nums, int target, int lo, int hi) {
// if (nums[lo] == target) return lo;
// if (nums[hi] == target) return hi;
// if (lo + 1 >= hi) return -1;
// int mid = lo + (hi - lo) / 2;
// if (nums[mid] == target) return mid;
// if (nums[mid] > nums[0]) {
// // means mid is in the left side of pivot
// if (nums[lo] <= target && target < nums[mid]) {
// return search(nums, target, lo, mid - 1);
// } else {
// return search(nums, target, mid + 1, hi);
// }
// } else {
// // means mid is in the right side of pivot
// if (nums[mid] < target && target <= nums[hi]) {
// return search(nums, target, mid + 1, hi);
// } else {
// return search(nums, target, lo, mid - 1);
// }
// }
// }
// 4.Recursive
// public int search(int[] nums, int target) {
// if(nums == null || nums.length == 0) return -1;
// if(nums.length == 1 && nums[0] == target) return 0;
// return search(nums, target, 0, nums.length - 1);
// }
// private int search(int[] nums, int target, int lo, int hi){
// if(lo > hi) return -1;
// int mid = lo + (hi - lo) / 2;
// if(nums[mid] == target) return mid;
// if(nums[mid] >= nums[lo]){
// if(nums[lo] <= target && target < nums[mid]) return search(nums, target, lo, mid - 1);
// else return search(nums, target, mid + 1, hi);
// }else{
// if(nums[mid] < target && target <= nums[hi]) return search(nums, target, mid + 1, hi);
// else return search(nums, target, lo, mid - 1);
// }
// }
}