ThinkSSL🔒 一键申购 5分钟快速签发 30天无理由退款 购买更放心 广告
**一. 题目描述** Given a sorted array of integers, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of `O(logn)`. If the target is not found in the array, return `[-1, -1]`. For example, Given `[5, 7, 7, 8, 8, 10]` and target value `8`, return `[3, 4]`. **二. 题目分析** 题目大意是,给定一个已排序的序列和一个目标数字`target`,在这个序列中寻找等于`target`的**元素的下标范围**。由于序列已经排好序,直接用二分查找,分别求等于`target`的最靠左的元素下标`left`和最靠右的元素下标`right`即可。 **三. 示例代码** ~~~ #include <iostream> #include <vector> using namespace std; class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { int n = nums.size(); int left = searchRangeIndex(nums, target, 0, n - 1, true); int right = searchRangeIndex(nums, target, 0, n - 1, false); vector<int> result; result.push_back(left); result.push_back(right); return result; } private: int searchRangeIndex(vector<int>& nums, int target, int low, int high, bool isLeft) { while (low <= high) { int midIndex = (low + high) >> 1; if (nums[midIndex] == target) { int temp = -1; if (isLeft) { if (nums[midIndex] == nums[midIndex - 1] && low < midIndex) temp = searchRangeIndex(nums, target, low, midIndex - 1, true); } else { if (nums[midIndex] == nums[midIndex + 1] && high > midIndex) temp = searchRangeIndex(nums, target, midIndex + 1, high, false); } return temp == -1 ? midIndex : temp; // temp == -1时表示只有中间一个值等于target } else if (nums[midIndex] > target) high = midIndex - 1; else low = midIndex + 1; } return -1; // 找不到target,输出-1 } }; ~~~ ![](https://box.kancloud.cn/2016-01-05_568bb5f1c162b.jpg) **四. 小结** 注意题目要求`O(logn)`的时间复杂度,算法写的不好可能会超时。