Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

The title

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:

Input: nums = [5,7,7,8,8,10] target = 8

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6

Example 3:

Input: nums = [], target = 0 output: [-1,-1]

 

Tip:

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

Their thinking

In this paper, we will find a better solution from O(n) to O(logn). By Nalan Xingde “Magnolia Ling · Fictive ancient Renunciation” to illustrate the characteristics of the solution

1. The cycle

  • traversefirsttargetThe assignmentStart aandStop bits. goodbyetargetUpdate onlyStop bitsUp to the current number>The target

code

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

2. A hash table

  • Object hash tableThe current number ofAs aKey name. First assignment. Goodbye update onlyStop bits. And you get all the numbersStart-stop position

code

var searchRange = function(nums, target) {
    return nums.reduce((h, v, i) = > (h[v] ? h[v][1] = i : h[v] = [i, i], h), Object.create(null))[target] || [-1, -1]};Copy the code
  • contrastcycleThe solution, we didn’t use itascendingProperties. thoughoverqualifiedBut, forAll the number, is theNothing changes, nothing changesThe solution of

3. Binary search

  • Take the middle number for each round. Greater than the target value, continue looking for the left half. Less than the target, keep looking for the right half
  • If not found, return- 1. Find and center on itSpread aroundLooking for aDoes not equal the target valueandDon't crossThe boundary of the

code

var searchRange = function(nums, target) {
    var i = binarySearch(nums, target)
    if (i === -1) return [-1, -1]
    else {
        var l = i, r = i + 1
        while(nums[l] === target && l >= 0) l--
        while(nums[r] === target && r < nums.length) r++
    }
    return [l + 1, r - 1]};var binarySearch = (nums, target, l = 0, r = nums.length - 1, m = l + r >>> 1) = > 
          l  >  r      ? -1 :
    nums[m] === target ?  m :
    nums[m]  >  target ? binarySearch(nums, target, l, m - 1)
                       : binarySearch(nums, target, m + 1, r)
Copy the code
  • The candidate reductionAnd a half, speed up the dichotomy comparison
    • Binary search: the search complexity is stableO(logn). Sequential storage, 100% utilization of space. Difficult to delete and insert
    • Binary search tree: The search complexity is idealO(logn)The depth ofnAs for theO(n)

Chain storage, Pointers take up extra space. Delete inserts by simply moving the pointer

Binary search

  • The difference betweenIs that whennums[m] === target, the above solution, directly return the value
  • This solution, findThe left border, continue toLook left. findThe right boundary, continue toTo find the rightAs shown in figure
  • l > rWhen to return toThe right boundary. suchThe left borderWill be the firstThe targetOn the left side,The right boundaryWill be toThe targetLast bit

code

var searchRange = function(nums, target) {
    var l = binarySearch(nums, target, true), r = binarySearch(nums, target, false)
    return l === r ? [-1, -1] : [l + 1, r]                            
};
var binarySearch = (nums, target, isL, l = 0, r = nums.length - 1, m = l + r >>> 1) = > 
    l  >  r ? r : (isL ? nums[m] >= target : nums[m] > target)
            ? binarySearch(nums, target, isL, l, m - 1)
            : binarySearch(nums, target, isL, m + 1, r)
Copy the code
  • 2,2,2,2,2,2 [...]. target = 2The example is solved aboveSpread around, will degenerate intoO(n)
  • colorfulOnly birdA wing, it is necessary toTwo fly together.2aBinary searchTime complexity can be stabilized
  • Why is itl > rWhy returnr? Because you have to think aboutFour boundary casesAs shown in figure







  • The above4 kinds of circumstancesSo this is binary searchThe borderSituation, exactlyThe borderIt helps us determineconditionsAnd returnPointer to the