“This is the 15th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Given an ascending array and a target value, find where the target value begins and ends in the array. If the target value does not exist, return [-1, -1]. The required time complexity is O(logN)O(logN)O(logN).

Their thinking

Ordered array, O(logN)O(logN)O(logN) O(logN), the first thing to think of is dichotomy, forget about the time. Because the array is ordered, we can scan the array from front to back and from back to front respectively. If the element on the left is equal to the target value, we record it. This ensures that the element is the first one from front to back, and the same ensures that the element on the right is the first one from back to front.

public static int[] searchRange(int[] nums, int target) {
        int left=-1, right=-1;
        int l=0, r=nums.length-1;
        while(l<=r){
            if(nums[l]==target){
                left = l;
            }else {
                l++;
            }

            if(nums[r]==target){
                right = r;
            }else {
                r--;
            }

            if(left! = -1&&right! = -1) {break; }}return new int[]{left, right};
    }
Copy the code

The actual running time is 1ms, the time complexity of the above code is O(N)O(N)O(N) O(N), and the space complexity is O(1)O(1)O(1) O(1). The idea is like a double pointer, so how do you use dichotomy here? Nums [mid]==target; nums[mid-1]=nums[mid+1]=target;

Convert the idea to:

  1. Find the first index in an array that is larger than an element.
  2. That is to look for greater thantarget-1The first index of, if presenttargetThe first index of.
  3. Looking for more thantargetThe first index, if presentindex-1Is thetargetThe last index of the.

Index must be initialized to the length of the array, because if there is no element greater than target in the array, target must be the last element in the array, and the length of the array should be returned if the index-1 is needed later. The code is as follows:

public static int[] searchRange2(int[] nums, int target) {
        int left = binarySearch(nums, target-1);
        int right = binarySearch(nums, target) - 1;
        if(left<=right){
            return new int[]{left, right};
        }
        return new int[] {-1, -1};

    }

    public static int binarySearch(int[] nums, int target){
        int l=0, n=nums.length, r=n-1, index=n; // Index must be an array length, otherwise an error is reported
        while (l<=r){
            int mid = (l + r) / 2;
            if(nums[mid]>target){
                r=mid-1;
                index=mid;
            }else {
                l=mid+1; }}return index;
    }
Copy the code

Because the above algorithm is binary search, the time complexity of its algorithm is O(logN)O(logN)O(logN) O(logN), the algorithm uses constant variables, and the space complexity is O(1)O(1)O(1) O(1).