“This is the 19th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”.

1, the title

Given an array of integers in ascending order, nums, and a target value, target. Find the starting and ending positions of the given target value in the array.

If no target value exists in the array, return [-1, -1].

Advanced:

  • You can design and implement a time complexity of zeroO(log n)Does the algorithm solve this problem?

Example 1:

Input: nums = [5,7,7,8,8,10] target = 8Copy the code

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6Copy the code

Example 3:

Input: nums = [], target = 0 output: [-1,-1]Copy the code

Tip:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • numIs a non-decrement array
  • -109 <= target <= 109

2, train of thought

(dichotomy)O(logn)O(logn) O(logn)

To find a number in a range, you need to find the beginning and end positions of this element. The numbers in this range are monotonically increasing, that is, they have monotone properties, so you can use dichotomy to do it.

Double dichotomy, the first dichotomy looks for the location of the first >=target and the second dichotomy looks for the location of the last <=target. Returns two position subscripts on success, otherwise returns [-1,-1].

Implementation details:

  • In binary search, we should first determine the boundary value we are looking for, and ensure that the boundary value is always included every time the dichotomy reduces the interval.

First search start position:

  • L = 0, r = nums.size() -1, l = 0, r = nums.size() -1, r = nums.size() -1

  • If nums[mid] >= target, r = mid

  • If nums[mid] < target, l = mid + 1

  • 4, ifnums[r] ! = target, indicating that the target value does not exist in the arraytargetTo return to[1, 1]. Otherwise we would have found our first one>=targetThe location of theL.

End location of the second search:

  • L = 0, r = nums.size() -1, l = 0, r = nums.size() -1

  • If nums[mid] <= target, l = mid

  • If nums[mid] > target, r = mid – 1

  • Select * from target where R <=target;

Time complexity analysis: The time complexity of two binary search is O(logn)O(logn)O(logn).

C++ code

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.empty()) return {- 1.- 1};
    
        int l = 0, r = nums.size() - 1; // Binary range
        while( l < r)			// Find the starting position of the element
        {
            int mid = (l + r )/2;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if( nums[r] ! = target)return {- 1.- 1};
        int L = r;
        l = 0, r = nums.size() - 1;
        while( l < r)          // Find the end of the element
        {
            int mid = (l + r + 1) /2;
            if(nums[mid] <= target ) l = mid;
            else r = mid - 1;
        }
        return{L,r}; }};Copy the code

4. Java code

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums.length == 0) return new int[] {-1, -1};
    
        int l = 0, r = nums.length - 1; // Binary range
        while( l < r)			// Find the starting position of the element
        {
            int mid = (l + r )/2;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if( nums[r] ! = target)return new int[] {-1, -1};
        int L = r;
        l = 0; r = nums.length - 1;
        while( l < r)			// Find the end of the element
        {
            int mid = (l + r + 1) /2;
            if(nums[mid] <= target ) l = mid;
            else r = mid - 1;
        }
        return new int[]{L,r}; }}Copy the code

Original link: 34. Find the first and last positions of elements in a sorted array