Illustration of LeetCode brush problem plan

1. Write it first

Hand-drawn comic book series officially launched!!” LeetCode brush plan “here it comes!!

Today is the 16th issue, strive for a daily issue, at most two days, welcome everyone to supervise me…

Template summary:

  • 【 freehand caricature 】 Two parts of the interview to find (solution template and in-depth analysis), last time
  • No longer afraid of girlfriend to ask me dichotomy search! Binary Search (Revised edition) (LeetCode 704)
  • No longer afraid of girlfriend to ask me dichotomy search!! 【 freehand cartoon 】 The interview must test two search (solution template and in-depth analysis), the final answer

Issues left over from history:

Don’t worry, let’s look at today’s problem.

2, the topic

So let’s look at the problem first,

And then, by accident, I discovered the secret.

3, the body

Let’s see what the secret is.

The first sequence is 5, 7, 7, 8, 10, target=7.

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;
Copy the code

mid
right

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;
Copy the code

mid
left

The last value returned is left or right! Because the condition at the end of while is left and right are 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}; }};Copy the code

If lucky enough to help you, please help me a [praise], to a [attention]! I would appreciate an encouragement along the way.

If you want more resources, please follow @I’m Guan Xiaoliang, MAX~