The illustration LeetCode Brush question plan

1、 Write it at the front

Hand drawn cartoon series officially launched ！！！“ The illustration LeetCode Brush question plan ” coming ！！！

Today is issue 16 , Strive for one issue a day , Up to two days , You are welcome to supervise me ...

Template summary ：

• 【 Hand drawn cartoon 】 Two parts of the interview must be searched （ Problem solving template and depth analysis ）, Last
• I'm not afraid that my girlfriend will ask me for a binary search ！【 Hand drawn cartoon 】 Figure binary search （ Revised edition ）（LeetCode 704 topic ）
• I'm not afraid that my girlfriend will ask me for a binary search ！！！【 Hand drawn cartoon 】 Two parts of the interview must be searched （ Problem solving template and depth analysis ）, Final return

an issue rooted in history ：

What is the difference between the two templates ？？？

take it easy , Let's look at today's question .

2、 subject

First look at the topic ,

Normal binary search , There's a limit to repetition , In addition, the head and tail positions of repeating elements are required .

And then inadvertently , I found the secret .

3、 Text

Let's see what the secret is ？

The first sequence is 5、7、7、8、10,target=7, Search by template 1 / 2 .

int left=0;
int right=nums.size()-1;
while(left<right){

int mid=left+right>>1;
if(nums[mid]>=target){

right=mid;
}
else{

left=mid+1;
}
}
return left;

You can see , It returns the value on the left ,mid It's going down ,right It's also , therefore ~

And template two ？

int left=0;
int right=nums.size()-1;
while(left<right){

int mid=(left+right+1)>>1;
if(nums[mid]<=target){

left=mid;
}
else{

right=mid-1;
}
}
return right;

You can see , It returns the value on the right ,mid It's going up ,left It's also , therefore ~

The last returned value is written as left perhaps right No problem ！ because while The end condition of is left and right equal .

4、 Code

class Solution {

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

if(nums.empty()) return {
-1,-1};
int left=0;
int right=nums.size()-1;
while(left<right){

int mid=(left+right)>>1;
if(nums[mid]>=target){

right=mid;
}
else{

left=mid+1;
}
}
if(nums[left]!=target) return {
-1,-1};
int start=left;
left=0;
right=nums.size()-1;
while(left<right){

int mid=(left+right+1)>>1;
if(nums[mid]<=target){

left=mid;
}
else{

right=mid-1;
}
}
if(nums[left]!=target) return {
-1,-1};
int end=right;
return {
start,end};
}
};

If I have the honor to help you , Please order one for me 【 Fabulous 】, Give me one 【 Focus on 】！ If you can bring along 【 Comment on 】 Give me a piece of encouragement , I would be grateful .

If you want more resources , Welcome to your attention @ I'm Guan Xiaoliang , Obsessive compulsive disorder MAX~