This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

Source: LeetCode

Link: leetcode-cn.com/problems/fi…

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:

Enter nums = [5,7,7,8,8,10], target = 8

Output: [3, 4]

Example 2:

Enter nums = [5,7,7,8,8,10], target = 6

Output: [1, 1]

Example 3:

Enter: nums = [], target = 0

Output: [1, 1]

Tip:

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

Subject analysis

The general solution

Without further explanation, just walk through it from left to right, finding the first element and target, and then the second

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        int len = nums.length;
        if(len == 0 || nums[0] > target || nums[len - 1] < target){
            return result;
        }

        boolean flag = true;
        for (int i = 0; i < len; i++) {
            if (nums[i] == target){
                if(flag){
                    result[0] = i;
                    flag = false; }}if(! flag && nums[i] ! = target) { result[1] = i - 1;
                break; }}if((len == 1 && nums[0] == target)){
            result[1] = 0;
        }

        if(nums[len - 1] == target) {
            result[1] = len - 1;
        }
        returnresult; }}Copy the code

Order n time, and then challenge the order log n solution

Binary search

  • The combination of order and array is definitely binary lookup

  • The first thing is to find the leftmost index, use binary search to find a value that is equal to the target value, and then because we are looking for the leftmost index, so right=mid-1 all the way to the left to get to the leftmost value

  • So to find the right most index, I’m going to take left=mid+1 and approach the right most index

  • If not found, it does not exist and returns -1

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int [] result = {-1, -1};
        result[0] = findLeftIndex(nums,target);
        result[1] = findRightIndex(nums,0,target);
        return result;
    }
    public int findLeftIndex(int [] nums,int target)
    {
        int left = 0;
        int right = nums.length - 1;
        int leftIndex = -1;
        while(left <= right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target)
            {
                left = mid + 1;
            }else if(nums[mid] > target)
            {
                right = mid - 1;
            }else{
                leftIndex = mid;
                right = mid - 1; }}return leftIndex;
    }
    public int findRightIndex(int [] nums,int left,int target)
    {

        int right = nums.length - 1;
        int rightIndex = -1;
        while(left <= right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target)
            {
                left = mid + 1;
            }else if(nums[mid] > target)
            {
                right = mid - 1;
            }else{
                rightIndex = mid;
                left = mid + 1; }}returnrightIndex; }}Copy the code

conclusion

The idea of this solution is very clear, but some boundary conditions need to be determined. Binary search time order (\log n)

Here’s a simple binary search, for example, for the array [1,2,4,4,4,4, 5,6], find the leftmost index of 4.

  • Left =0,right =8, so mid=(0+8)/2 = 4;

  • Since target=4 is equal to nums[mid], we record the index, which is the value of mid 4. This index is the left-most possible index of 4.

  • If you look at the array, you can see that the left-most index of 4 is 2, so in order to find the left-most index, you need to set right to equal mid-1; So I’m going to move the right side slowly to the left, because I’m looking for the leftmost, so I’m going to shrink the right side to get to the leftmost 4, until I find the leftmost 4;

  • The same idea is used to find the rightmost 4, which is to set left=mid+1 to approximate the rightmost 4.