This is the 12th day of my participation in Gwen Challenge

The topic of dry

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:

Can you design and implement an O(log n) algorithm to 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

Idea 1: Dual Pointers

If a pointer reaches target and stops until both ends stop, the loop will record and exit.

Code implementation:

Execution time: 80 ms, beating 86.54% of users in all JavaScript commits

Memory consumption: 39.3 MB, beating 49.99% of all JavaScript commits

var searchRange1 = function (nums, target) {
    / / double pointer
    let index = 0;
    let indey = nums.length - 1;
    while (index <= indey) {
      if (nums[index] == target && nums[indey] == target) {
        return [index, indey]
      }
      if(nums[index] ! = target) { index++ }else if(nums[indey] ! = target) { indey-- } }return [-1, -1]};Copy the code

Idea 2: Binary search

This problem is divided into two dichotomies, respectively to find the starting position of the repeated interval, how to find the actual position of the interval?

It’s pretty simple, but if we find the tartget value and continue to divide, if we’re looking for the left boundary value, we move the Max pointer to the tartget value, and if we’re looking for the right boundary value, we move the min pointer to the tartget value.

Note: It should be noted that when we are looking for interval values, it is not enough to simply assign the value of mid to min, because this may cause the min pointer to stay in place and eventually lead to an infinite loop, so we need to add the value of mid to +1 every time we loop

The handwriting is not fair, but it is illustrative

Code implementation:

Execution time: 64 ms, beating 99.90% of users in all JavaScript commits

Memory consumption: 39.1 MB, beating 83.43% of all JavaScript commits

 var searchRange = function (nums, target) {
    let firstTartget = getFirstTartget(nums, target);
    let lastTarget = getlastTarget(nums, target);
    if (firstTartget == -1) {
      return [-1, -1]}return [firstTartget, lastTarget]
  };
	// find the left interval
  function getFirstTartget(nums, target) {
    let min = 0;
    let max = nums.length - 1;
    while (min < max) {
      let mid = min + Math.floor((max - min) / 2)
      if (nums[mid] > target) {
        max = mid - 1
      } else if (nums[mid] < target) {
        min = mid + 1
      } else {
        max = mid
      }
    }
    return nums[max] == target ? max : -1
  }
	// find the right interval
  function getlastTarget(nums, target) {
    let min = 0;
    let max = nums.length - 1;
    while (min < max) {
      let mid = min + Math.floor((max - min) / 2) + 1
      if (nums[mid] > target) {
        max = mid - 1
      } else if (nums[mid] < target) {
        min = mid + 1
      } else {
        min = mid
      }
    }
    return min
  }
  console.log(searchRange([5.7.7.8.8.10].6))
Copy the code