This is the 24th day of my participation in the More text Challenge. For more details, see more text Challenge

Find the first and last position of an element in a sorted array (question 34)

The title

Given an array of ascending integers, nums, and a target value. Find the start and end positions in the array for the given target value.

Return [-1, -1] if there is no target value in the array.

Advanced:

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

Example 1:

Input: nums = [5.7.7.8.8.10], target = 8Output:3.4]
Copy the code

Example 2:

Input: nums = [5.7.7.8.8.10], target = 6Output: [...1, -1]
Copy the code

Example 3:

Nums = [], target =0Output: [...1, -1]
Copy the code

Tip:

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

link

Leetcode-cn.com/problems/fi…

explain

This one, this is a classic dichotomy.

The simple solution is really simple, because it’s a non-descending array, and notice, I’m using a non-descending array, because there are repeating elements in an array, so a non-descending array is more appropriate.

If the target is not in descending order, return [-1, -1]. If the target is not in descending order, return [-1, -1].

This can be written in one line of code 👇 :

var searchRange = function(nums, target) {
  return nums.reduce((position, value, index) = > {
    return value === target ? [position[0] = = = -1 ? index : position[0], index] : position
  }, [-1, -1])};Copy the code

If the value of the current element is larger than the target, it will be broken because it is a non-descending array 👇 :

var searchRange = function(nums, target) {
  return nums.reduce((position, value, index) = > {
    return value === target ? [position[0] = = = -1 ? index : position[0], index] : (value > target && (nums.length = 0), position)
  }, [-1, -1])};Copy the code

After a few attempts, the improvement was quite good, but the feeling was influenced by the test case. For example, if the array length is 1W and the elements of the compound condition are in the first 10, then the pruning is done well, saving a lot of calculation.

So the point here is to implement an algorithm that has order log n time, so when you see order log n times, you know it’s binary, it’s obvious time.

The dichotomy is basically divided into two parts, the first part is the regular dichotomy, find the element or just return it. The second part is because the array here is a non-descending array, so there are duplicate numbers, so you have to expand both sides, find all the same values, and then you get the range.

Your own answer (traversal)

var searchRange = function(nums, target) {
  return nums.reduce((position, value, index) = > {
    return value === target ? [position[0] = = = -1 ? index : position[0], index] : (value > target && (nums.length = 0), position)
  }, [-1, -1])};Copy the code

This method has been mentioned before, so I won’t go into it here.

Your own answer (dichotomy + diffusion)

var searchRange = function(nums, target) {
  var left = 0
      right = nums.length - 1
  while (left < right) {
    var mid = ~~((left + right) / 2)
    if (nums[mid] === target) {
      left = mid
      right = mid
    } else if (nums[mid] < target) {
      left = mid + 1
    } else {
      right = mid - 1}}if(nums[left] ! == target)return [-1, -1]
  while (nums[left] === target || nums[right] === target) {
    if (nums[left] === target) left--
    if (nums[right] === target) right++
  }
  return [left + 1, right - 1]};Copy the code

The first while is the classical dichotomy, and the second while is the center diffusion, finding all the values that fit, and getting the final interval.

That’s the easy one.

Better method (dichotomy + positioning interval)

This is the official answer, mainly using dichotomous thinking.

Take a look at the code 👇 :

const binarySearch = (nums, target, lower) = > {
  let left = 0, right = nums.length - 1, ans = nums.length;
  while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      if (nums[mid] > target || (lower && nums[mid] >= target)) {
          right = mid - 1;
          ans = mid;
      } else {
          left = mid + 1; }}return ans;
}

var searchRange = function(nums, target) {
  let ans = [-1, -1];
  const leftIdx = binarySearch(nums, target, true);
  const rightIdx = binarySearch(nums, target, false) - 1;
  if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] === target && nums[rightIdx] === target) {
      ans = [leftIdx, rightIdx];
  } 
  return ans;
};
Copy the code

The binarySearch method is defined to perform a binarySearch, but this is not a typical binarySearch. Instead, there is a little transformation. Note that the third argument, lower, is a Boolean value.

The last two times we call this method, we find the left and right interval value, if the condition is met, we return the left and right interval value, otherwise we return [-1. -1].

This is not always the case, though. If the target is repeated many times, the performance of this method will be better, and if the target is not repeated many times, it will feel better as binary + diffusion.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ