当前位置:网站首页>[binary search] 34 Find the first and last positions of elements in a sorted array
[binary search] 34 Find the first and last positions of elements in a sorted array
2022-07-05 05:16:00 【lee2813】
One 、 subject
Given an array of integers in ascending order nums, And a target value target. Find the start and end position of the given target value in the array .
If the target value does not exist in the array target, return [-1, -1].
Advanced :
You can design and implement time complexity of O(log n) Does the algorithm solve this problem ?
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]
Example 3:
Input :nums = [], target = 0
Output :[-1,-1]
Two 、 Answer key
Solution 1 : Search for ( Time consuming )
Solution 2 : Two points search
Because the array is monotonically increasing , We can use the binary search method to speed up the search process . Here is also set as the left closed right closed interval .
When finding the corresponding element to determine whether it is the position of the first occurrence and the last occurrence of the given value , Use the following strategies :
- Finding the first occurrence position of a given value is equivalent to finding the first greater than ( Because there may be cases without this value ) Subscript equal to the given value
- Finding the last occurrence position of a given value is equivalent to finding the first subscript larger than the given value , subtracting 1
Take finding the location of the first occurrence as an example , The search results are as follows :
- The lookup value does not match the target value ( Less than the target ): Take the left range
- The search value matches the target value ( Greater than equal target value ): Take the right range
- Left boundary > Right border : return
l
, Because the matching situation here is greater than or equal to , Moving isl
, Therefore, it returnsl
among , The method of using dichotomy to determine the position of elements for comparison is the same , The comparison strategy is different .
3、 ... and 、 Code
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.size()==0) return vector<int>{
-1,-1};
int leftindex = fun1(nums,target);
int rightindex = fun2(nums,target);
if(leftindex==nums.size() || nums[leftindex] != target) return vector<int>{
-1,-1};
return vector<int>{
leftindex,rightindex};
}
int fun1(vector<int>& nums,int target){
int l = 0,r = nums.size() - 1;
int mid;
while(l<=r){
mid = (l + r) / 2;
if(nums[mid] >= target) r = mid - 1;
else l = mid + 1;
}
return l;
}
int fun2(vector<int>& nums,int target){
int l = 0,r = nums.size() - 1;
int mid;
while(l<=r){
mid = (l + r) / 2;
if(nums[mid] > target) r = mid - 1;
else l = mid + 1;
}
return l-1;
}
};
边栏推荐
猜你喜欢
嵌入式数据库开发编程(六)——C API
Recherche de mots pour leetcode (solution rétrospective)
[转]MySQL操作实战(三):表联结
2022年上半年国家教师资格证考试
Learning notes of "hands on learning in depth"
小程序直播+电商,想做新零售电商就用它吧!
C4D simple cloth (version above R21)
Embedded database development programming (zero)
C language Essay 1
How to choose a panoramic camera that suits you?
随机推荐
Chinese notes of unit particle system particle effect
Bubble sort summary
Dotween usage records ----- appendinterval, appendcallback
TF-A中的工具介绍
Animation
Unity ugui source code graphic
Listview is added and deleted at the index
Under the national teacher qualification certificate in the first half of 2022
SDEI初探-透过事务看本质
Three dimensional dice realize 3D cool rotation effect (with complete source code) (with animation code)
Redis has four methods for checking big keys, which are necessary for optimization
Lua determines whether the current time is the time of the day
3dsmax scanning function point connection drawing connection line
Data is stored in the form of table
Ue4/ue5 illusory engine, material chapter, texture, compression and memory compression and memory
[paper notes] multi goal reinforcement learning: challenging robotics environments and request for research
十年不用一次的JVM调用
How much do you know about 3DMAX rendering skills and HDRI light sources? Dry goods sharing
Solon Logging 插件的添加器级别控制和日志器的级别控制
Fragment addition failed error lookup