preface

Find the first and last positions of the elements in the sorted array as follows:

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].

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

A, thinking

After reading the questions carefully, you can get the following two important messages:

  • Sort an array in ascending order
  • Find the position of the target value (start and end positions)

You can ignore where the target value starts and ends. For ascending arrays, dichotomy is the best way to find the target value.

The realization idea can be roughly divided into the following two steps:

  1. Use dichotomy to locate the target valuep, i.e.,nums[p] == target
  2. From the positionpForward to findStarting positionAnd then frompFind backEnd position

For example

Here, nums = [5,7,7,8,8,10] and target = 8 in example 1 are used as examples

P = -1: position of target value, initial value -1 left = 0: left boundary of dichotomy right = nums.lengt -1: right boundary of dichotomy

The specific steps are as follows:

  1. mid = (left + right)/2 = 2At this time,nums[mid] < targetOn the right side.left = mid + 1 = 3
  2. mid = (left + right)/2 = 4At this time,nums[mid] == targetWe have the target locationp = 4
  3. From the positionpForward,nums[3] == target
  4. Moving on,nums[2] ! = target, indicating that the start position is3
  5. From the positionpBackward,nums[5] ! = target, indicating that the end position is4
  6. Returns the result3 和 4

Second, the implementation

The implementation is consistent with the idea, but note that if the binary method does not find the target value, then return the result directly

The implementation code

    /** * dichotomy */
    public int[] searchRange(int[] nums, int target) {
        int[] ret = {-1, -1};
        int len = nums.length;
        int left = 0;
        int right = len - 1;
        // Find the target location first
        int p = -1;
        while (left <= right) {
            int mid = (left + right)/2;
            if (nums[mid] == target) {
                p = mid;
                break;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1; }}// Check if it is found
        if(p ! = -1) {
            // Look ahead
            int i = p;
            int j = p;
            // Look ahead
            for (; i>-1; i--) {
                if(nums[i] ! = target)break;
            }
            / / backward
            for (; j<nums.length; j++) {
                if(nums[j] ! = target)break;
            }
            / / assignment
            ret[0] = i + 1;
            ret[1] = j - 1;
        }
        return ret;
    }
Copy the code

The test code

Public static void main(String[] args) {int[] nums = {5,7,7,8,8,10}; int target = 8; new Number34().searchRange(nums, target); }Copy the code

The results of

Third, summary

Generally speaking, dichotomy is a good choice for finding target values in ascending or descending arrays!

Thank you to see the end, very honored to help you ~♥