【LeetCode & 剑指offer刷题】查找与排序题8：Search for a Range

古城微笑少年丶 2021-10-26 15:42 243阅读 0赞

**[【LeetCode & 剑指offer 刷题笔记】目录（持续更新中...）][LeetCode _ _offer _...]**

**Search for a Range**

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:**

**Input:** nums = \[ 5,7,7,8,8,10\] , target = 8

**Output:** \[3,4\]

**Example 2:**

**Input:** nums = \[ 5,7,7,8,8,10\] , target = 6

**Output:** \[-1,-1\]

--------------------

C+

类似： 53 数字在排序数组中出现的次数

/\*问题：在有序数组中查找目标值出现的范围

方法：对于有序序列用二分查找

使用stl中lower\_bound和upper\_bound函数

O(logn)

\*/

class Solution

**\{**

public **:**

vector **<** int **>** searchRange **(** vector **<** int **>&** nums **,** int target **)**

**\{**

**if** **(** nums **.** empty **())** **return** vector **<** int **>\{-** 1 **,-** 1 **\};** // 容器为空时 （ vector<int>\{\} 为初始化返回容器操作）

//lower\_bound 找到后返回第一个大于等于 target 的位置的迭代器，否则返回迭代器 end

vector **<** int **>::** iterator start **=** lower\_bound **(** nums **.** begin **(),** nums **.** end **(),** target **);**

//upper\_bound 找到后返回第一个大于 target 的位置的迭代器，否则返回迭代器 end

vector **<** int **>::** iterator end **=** upper\_bound **(** nums **.** begin **(),** nums **.** end **(),** target **);**

**if** **(** start **==** end **||** start **==** nums **.** end **())** // 相等时，说明找到的是大于目标值的数，指向 end 时说明目标值比数组所有元素大，两种情况下均为没有找到

**return** **\{-** 1 **,-** 1 **\};**

**else**

**return** **\{**  start **-** nums **.** begin **(),** end **-** nums **.** begin **()-** 1 **\};**

**\}**

**\};**

** **

/\*

//或者自己实现

class Solution \{

public:

vector<int> searchRange(vector<int>& nums, int target) \{

vector<int> result;

int begin = 0;

int end = nums.size() - 1;

int start\_index = -1;

int end\_index = -1;

//locate the start\_index

while (begin <= end)\{

int mid = (begin + end) / 2;

if (nums\[mid\] == target)\{

if (mid - 1<0 || nums\[mid - 1\] != target)\{

start\_index = mid;

break;

else\{

end = mid - 1;

else if (nums\[mid\]>target)\{

end = mid - 1;

else\{

begin = mid + 1;

//locate the end\_index

begin = 0;

end = nums.size() - 1;

while (begin <= end)\{

int mid = (begin + end) / 2;

if (nums\[mid\] == target)\{

if (mid + 1>nums.size() - 1 || nums\[mid + 1\] != target)\{

end\_index = mid;

break;

else\{

begin = mid + 1;

else if (nums\[mid\]>target)\{

end = mid - 1;

else\{

begin = mid + 1;

//cout << start\_index << " " << end\_index << endl;

result.push\_back(start\_index);

result.push\_back(end\_index);

return result;

\};

\*/

转载于:https://www.cnblogs.com/wikiwen/p/10225947.html

[LeetCode _ _offer _...]: https://blog.csdn.net/kk55guang2/article/details/85223256

【LeetCode & 剑指offer刷题】查找与排序题8：Search for a Range

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 [leetcode-二分查找]--34. Search for a Range

相关 [leetcode-二分查找]--34. Search for a Range

相关 leetcode 34. Search for a Range 二分查找

相关剑指offer——刷题集

相关剑指offer刷题

相关剑指offer刷题（二）

相关剑指offer刷题（一）

相关剑指offer刷题第一题

相关【LeetCode & 剑指offer刷题】查找与排序题8：Search for a Range

相关剑指offer刷题指南