一. 題目描述
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
#include
using namespace std;
class Solution {
public:
vector searchRange(vector& 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 result;
result.push_back(left);
result.push_back(right);
return result;
}
private:
int searchRangeIndex(vector& 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
}
};
四. 小結
注意題目要求O(logn)
的時間復雜度,算法寫的不好可能會超時。