Solution: find the position of the first and last element in a sorted array (personal notes)

subject

Give you an array of integers in non decreasing order nums, And a target value target. Please find out the start position 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].

You must design and implement a time complexity of O(log n) The algorithm to 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]

Tips ：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums It is a group of non decreasing numbers
-109 <= target <= 109

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array

Their thinking

Use binary search

Because the array given is sorted in ascending order , So the conventional dichotomy , Judge whether there is any connection with target Equal value
If there is , Through i++, Come from i->mid Loop through to find the first and target The following table of equal array values i, After finding break;
Re pass j–, Come from mid->j Loop through to find the first and target The following table of equal array values j, After finding break;
Finally back to return {i,j};

If none of the above is satisfied , Then return to return {-1,-1};

Time complexity O(n^2)

Code

class Solution {
    
public:
    vector<int> searchRange(vector<int>& nums, int target) {
    
     int i = 0 , j = nums.size()-1,mid=0;
    
     while(i<=j)
     {
    
         mid = i + (j-i)/2;
         if(nums[mid]>target)j=mid-1;
         else if(nums[mid]==target)
         {
      
             for(;i<=mid;i++)
             {
    
                 if(nums[i]==target){
    break;}
             }
             for(;j>=mid;j--)
             {
    
                if(nums[j]==target){
    break;} 
             }        
          return {
    i,j};
         } 
         else i = mid+1;
     }     
    return {
    -1,-1};
    }
};

Optimize ：

Through the analysis of , I can give you a bool Type to judge , If... Exists in the array nums[mid]==target;
be bool Value of type is true , Otherwise it is false ;

Then put the original in while In circulation for Put it in while Outside the loop
In this way, the time complexity becomes O(log2^n)

Code

class Solution {
    
public:
    vector<int> searchRange(vector<int>& nums, int target) {
    
     int i = 0 , j = nums.size()-1,mid=0;
     bool k = false;
      while(i<=j)
     {
    
         mid = i + (j-i)/2;
         if(nums[mid]>target)j=mid-1;
         else if(nums[mid]==target)
         {
      
             k = true;break; 
         } 
         else i = mid+1;
     }
     if(k)
     {
      for(;i<=mid;i++)
             {
    
                 if(nums[i]==target){
    break;}
             }
             for(;j>=mid;j--)
             {
    
                if(nums[j]==target){
    break;} 
             }        
          return {
    i,j};
    }
         
    return {
    -1,-1};
    }
};