Skip to content

Commit 50c39ab

Browse files
fluency03fluency03
committed
SearchForARange34
1 parent 324a01b commit 50c39ab

2 files changed

Lines changed: 138 additions & 1 deletion

File tree

‎README.md‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@
99

1010

1111

12-
Total: **35**
12+
Total: **36**
1313

1414

1515
| Question | Solution | Difficulty |
@@ -22,6 +22,7 @@ Total: **35**
2222
| [16. 3Sum Closest](https://leetcode.com/problems/3sum-closest/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/ThreeSumClosest16.java) | Medium |
2323
| [20. Valid Parentheses](https://leetcode.com/problems/valid-parentheses/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/ValidParentheses20.java) | Easy |
2424
| [22. Generate Parentheses](https://leetcode.com/problems/generate-parentheses/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/GenerateParentheses22.java) | Medium |
25+
| [34. Search for a Range](https://leetcode.com/problems/search-for-a-range/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/SearchForARange34.java) | Medium |
2526
| [35. Search Insert Position](https://leetcode.com/problems/search-insert-position/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/SearchInsertPosition35.java) | Easy |
2627
| [41. First Missing Positive](https://leetcode.com/problems/first-missing-positive/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/FirstMissingPositive41.java) | Hard |
2728
| [46. Permutations](https://leetcode.com/problems/permutations/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/Permutations46.java) | Medium |

‎src/SearchForARange34.java‎

Lines changed: 136 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,136 @@
1+
/**
2+
* Given an array of integers sorted in ascending order, find the starting and
3+
* ending position of a given target value.
4+
*
5+
* Your algorithm's runtime complexity must be in the order of O(log n).
6+
*
7+
* If the target is not found in the array, return [-1, -1].
8+
*
9+
* For example,
10+
* Given [5, 7, 7, 8, 8, 10] and target value 8,
11+
* return [3, 4].
12+
*/
13+
14+
15+
16+
public class SearchForARange34 {
17+
public int[] searchRange(int[] nums, int target) {
18+
19+
int start = 0;
20+
int end = nums.length - 1;
21+
22+
while (start <= end) {
23+
if (nums[start] < target) {
24+
start++;
25+
} else if (nums[end] > target) {
26+
end--;
27+
} else {
28+
break;
29+
}
30+
}
31+
32+
if (start > nums.length - 1 || end < 0 || start > end) {
33+
return new int[]{-1, -1};
34+
}
35+
36+
return new int[]{start, end};
37+
}
38+
39+
40+
41+
public int[] searchRange2(int[] nums, int target) {
42+
43+
int start = 0;
44+
int end = nums.length - 1;
45+
int mid = (end - start) >> 1 + start;
46+
47+
while (start <= end) {
48+
if (nums[mid] < target) {
49+
start = mid + 1;
50+
} else if (nums[mid] > target) {
51+
end = mid - 1;
52+
} else {
53+
break;
54+
}
55+
56+
mid = (end - start) / 2 + start;
57+
}
58+
59+
while (start <= end) {
60+
if (nums[start] < target) {
61+
start++;
62+
} else if (nums[end] > target) {
63+
end--;
64+
} else {
65+
break;
66+
}
67+
}
68+
69+
if (start > nums.length - 1 || end < 0 || start > end) {
70+
return new int[]{-1, -1};
71+
}
72+
73+
return new int[]{start, end};
74+
}
75+
76+
77+
/**
78+
* https://discuss.leetcode.com/topic/6327/a-very-simple-java-solution-with-only-one-binary-search-algorithm
79+
*/
80+
public int[] searchRange3(int[] A, int target) {
81+
int start = Solution.firstGreaterEqual(A, target);
82+
if (start == A.length || A[start] != target) {
83+
return new int[]{-1, -1};
84+
}
85+
return new int[]{start, Solution.firstGreaterEqual(A, target + 1) - 1};
86+
}
87+
88+
//find the first number that is greater than or equal to target.
89+
//could return A.length if target is greater than A[A.length-1].
90+
//actually this is the same as lower_bound in C++ STL.
91+
private static int firstGreaterEqual(int[] A, int target) {
92+
int low = 0, high = A.length;
93+
while (low < high) {
94+
int mid = low + ((high - low) >> 1);
95+
//low <= mid < high
96+
if (A[mid] < target) {
97+
low = mid + 1;
98+
} else {
99+
//should not be mid-1 when A[mid]==target.
100+
//could be mid even if A[mid]>target because mid<high.
101+
high = mid;
102+
}
103+
}
104+
return low;
105+
}
106+
107+
108+
/**
109+
* https://discuss.leetcode.com/topic/10692/simple-and-strict-o-logn-solution-in-java-using-recursion
110+
*/
111+
public int[] searchRange(int[] A, int target) {
112+
int[] range = {A.length, -1};
113+
searchRange(A, target, 0, A.length - 1, range);
114+
if (range[0] > range[1]) range[0] = -1;
115+
return range;
116+
}
117+
118+
public void searchRange(int[] A, int target, int left, int right, int[] range) {
119+
if (left > right) return;
120+
int mid = left + (right - left) / 2;
121+
if (A[mid] == target) {
122+
if (mid < range[0]) {
123+
range[0] = mid;
124+
searchRange(A, target, left, mid - 1, range);
125+
}
126+
if (mid > range[1]) {
127+
range[1] = mid;
128+
searchRange(A, target, mid + 1, right, range);
129+
}
130+
} else if (A[mid] < target) {
131+
searchRange(A, target, mid + 1, right, range);
132+
} else {
133+
searchRange(A, target, left, mid - 1, range);
134+
}
135+
}
136+
}

0 commit comments

Comments
 (0)