[LeetCode] 034. Search for a Range (Medium) (C++/Java)

索引：[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};elsereturn 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;}}

，可我，仍在旅行的路上徘徊。等待着每一辆经过的车，让我走到更远的地方。