题目介绍
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example 1:
1 | Input: nums = [5,7,7,8,8,10], target = 8 |
2 | Output: [3,4] |
Example 2:
1 | Input: nums = [5,7,7,8,8,10], target = 6 |
2 | Output: [-1,-1] |
解
1 | class Solution { |
2 | private: |
3 | int findLeft(vector<int>& nums, int target) { |
4 | int left = 0; |
5 | int right = nums.size() - 1; |
6 | int ret = -1; |
7 | while (left <= right) { |
8 | int mid = (right - left) / 2 + left; |
9 | if (nums[mid] == target) { |
10 | ret = mid; |
11 | right = mid - 1; |
12 | } else if (nums[mid] < target) { |
13 | left = mid + 1; |
14 | } else { |
15 | right = mid - 1; |
16 | } |
17 | } |
18 | return ret; |
19 | } |
20 | int findRight(vector<int>& nums, int target) { |
21 | int left = 0; |
22 | int right = nums.size() - 1; |
23 | int ret = -1; |
24 | while (left <= right) { |
25 | int mid = (right - left) / 2 + left; |
26 | if (nums[mid] == target) { |
27 | ret = mid; |
28 | left = mid + 1; |
29 | } else if (nums[mid] < target) { |
30 | left = mid + 1; |
31 | } else { |
32 | right = mid - 1; |
33 | } |
34 | } |
35 | return ret; |
36 | } |
37 | public: |
38 | vector<int> searchRange(vector<int>& nums, int target) { |
39 | vector<int> ret; |
40 | if (nums.size() == 0) { |
41 | ret.emplace_back(-1); |
42 | ret.emplace_back(-1); |
43 | return ret; |
44 | } |
45 | ret.emplace_back(findLeft(nums, target)); |
46 | ret.emplace_back(findRight(nums, target)); |
47 | return ret; |
48 | } |
49 | }; |
