preface

About the LeetCode array type problem related solutions, it can be seen that LeetCode array type problem before doing must see, classification solution summarized the problem, can be used to improve a single. If you think it is helpful, remember to give more likes and attention, thank you!

Topic describes

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.

Example 1: input: nums = [5,7,7,8,8,10], target = 8 output: [3,4]

Example 2: input: nums = [5,7,7,8,8,10], target = 6 output: [-1,-1]

Example 3: Input: nums = [], target = 0 Output: [-1,-1]

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

Answer key

  1. Violent solution, traversing the group record boundary, time complexity O(n)
  2. Binary search, find the left boundary and the right boundary respectively, according to the function of binary search g, set g respectively, to find the smallest element satisfying g. Order logn time.
/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number[]}* /
var searchRange = function (nums, target) {
  const leftBorder = () = > {
    let l = 0;
    let r = nums.length;
    while (l < r) {
      let m = l + Math.floor((r - l) / 2);
      if (nums[m] >= target) {  
        r = m;
      } else {
        l = m + 1; }}if(l >= nums.length || nums[l] ! = target) {return -1;
    }
    return l;
  };

  const rightBorder = () = > {
    let l = 0;
    let r = nums.length;
    while (l < r) {
      let m = l + Math.floor((r - l) / 2);
      if (nums[m] > target) {
        r = m;
      } else {
        l = m + 1;
      }
    }
    l--;
    if (l < 0|| nums[l] ! = target) {return -1;
    }
    return l;
  };

  const l = leftBorder();
  const r = rightBorder();
  return [l, r];
};
Copy the code