索引：[LeetCode] Leetcode 题解索引 (C++/Java/Python/Sql)
Github: https://github.com/illuz/leetcode
035. Search for a Range (Medium)
链接：
题目：https://leetcode.com/problems/search-for-a-range/
代码(github)：https://github.com/illuz/leetcode
题意：
在有序数组中找到一个数的范围。（由于数有反复）
分析：
还是二分搜索变形。
-
(C++)直接用 C++ STL 的
lower_bound和upper_bound偷懒。 - (Java)直接从普通的二分改一下即可了。
代码：
C++:
class Solution {
public:
vector<int> searchRange(int A[], int n, int target) {
int* lower = lower_bound(A, A + n, target);
int* upper = upper_bound(A, A + n, target);
if (*lower != target)
return vector<int> {-1, -1};
else
return vector<int>{lower - A, upper - A - 1};
}
};
Java:
public class Solution {
public int[] searchRange(int[] A, int target) {
int[] ret = new int[2];
ret[0] = ret[1] = -1;
int left = 0, right = A.length - 1, mid;
while (left <= right) {
if (A[left] == target && A[right] == target) {
ret[0] = left;
ret[1] = right;
break;
}
mid = (right + left) / 2;
if (A[mid] < target) {
left = mid + 1;
} else if (A[mid] > target) {
right = mid - 1;
} else {
if (A[right] == target) {
++left;
} else {
--right;
}
}
}
return ret;
}
}