[binary search] 34 Find the first and last positions of elements in a sorted array

Binary search basis

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 is l, Therefore, it returns l

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;
    }
};