当前位置:网站首页>[leetcode]Search for a Range
[leetcode]Search for a Range
2022-07-07 02:31:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack
A narrative statement of the problem :
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 ofO(log n).
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]
.
The basic idea :
This problem can be solved by binary search .
Suppose there is no target, In the O(lgn) Time is over .
Let's say there's... In the array target, If I found target after , Continue to dichotomy the content before and after Find this location pos .
- Ahead pos Need to meet A[pos] < target && A[pos+1] == target. pos+1 That is the starting position .
- hinder pos Need to meet A[pos] > target && A[pos-1] == target . pos-1 It's the end position .
Code :
vector<int> searchRange(int A[], int n, int target) { //C++
vector<int> result(2);
int low = 0, high = n-1;
int mid, begin = -1, end = -1;
while(low <= high)
{
mid = (low+high)/2;
if(A[mid] > target)
high = mid - 1;
else if(A[mid] < target)
low = mid + 1;
else
{
begin = mid;
end = mid;
//get begin
if(low <= begin -1){
while((low <= begin-1) && !(A[low]<target && A[low+1] == target) )
{
mid = (low + begin-1)/2;
if(A[mid] < target)
low = mid+1;
else begin = mid;
}
if(A[low]<target && A[low+1] == target)
begin = low+1;
}
//get end
if(high >= end+1){
while((high >= end+1) &&!(A[high]>target && A[high-1] == target))
{
mid = (high + end +1)/2;
if(A[mid] > target)
high = mid - 1;
else end = mid;
}
if(A[high]>target && A[high-1] == target)
end = high - 1;
}
break;
}
}
result[0] = begin;
result[1] = end;
return result;
}
Copyright notice : This article is the original article of the blogger , Blog , Do not reprint without permission .
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/116862.html Link to the original text :https://javaforall.cn
边栏推荐
- Sensor: introduction of soil moisture sensor (xh-m214) and STM32 drive code
- Web开发小妙招:巧用ThreadLocal规避层层传值
- go swagger使用
- Collection recommandée!! Quel plug - in de gestion d'état flutter est le plus fort? Regardez le classement des manons de l'île, s'il vous plaît!
- TiFlash 源码阅读(四)TiFlash DDL 模块设计及实现分析
- Go swagger use
- unity中跟随鼠标浮动的面板,并可以自适应文字内容的大小
- Application analysis of face recognition
- UC伯克利助理教授Jacob Steinhardt预测AI基准性能:AI在数学等领域的进展比预想要快,但鲁棒性基准性能进展较慢
- String or binary data will be truncated
猜你喜欢
unity 自定义webgl打包模板
Zhang Ping'an: accelerate cloud digital innovation and jointly build an industrial smart ecosystem
C # / vb. Net supprime le filigrane d'un document word
Web3对法律的需求
Alibaba cloud middleware open source past
机器人队伍学习方法,实现8.8倍的人力回报
FLIR blackfly s usb3 industrial camera: how to use counters and timers
建议收藏!!Flutter状态管理插件哪家强?请看岛上码农的排行榜!
Increase 900w+ playback in 1 month! Summarize 2 new trends of top flow qiafan in station B
建議收藏!!Flutter狀態管理插件哪家强?請看島上碼農的排行榜!
随机推荐
机器人队伍学习方法,实现8.8倍的人力回报
Lumion 11.0软件安装包下载及安装教程
Application analysis of face recognition
Draco - glTF模型压缩利器
新一代云原生消息队列(一)
【Unity】升级版·Excel数据解析,自动创建对应C#类,自动创建ScriptableObject生成类,自动序列化Asset文件
[unity notes] screen coordinates to ugui coordinates
遇到慢SQL该怎么办?(下)
[paper reading | deep reading] dngr:deep neural networks for learning graph representations
PCL 常用拟合模型及使用方法
[server data recovery] data recovery case of a Dell server crash caused by raid damage
真实项目,用微信小程序开门编码实现(完结)
STM32项目 -- 选题分享(部分)
Zhang Ping'an: accelerate cloud digital innovation and jointly build an industrial smart ecosystem
【论文阅读|深读】ANRL: Attributed Network Representation Learning via Deep Neural Networks
C#/VB. Net to delete watermarks in word documents
Pgadmin4 of PostgreSQL graphical interface tool
猿桌派第三季开播在即,打开出海浪潮下的开发者新视野
Integerset of PostgreSQL
Use of pgpool II and pgpooladmin