## Finally know the difference between the two templates! [hand drawn cartoon] illustration of finding the first and last position of elements in sorted array (leetcode 34)

I'm Guan Xiaoliang 2020-11-13 05:30:31
finally know difference templates hand

# 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 ：

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~