The first questionFinds the first and last position of an element in a sorted array

Key points in this question

  • ascending
  • Find the start and end positions of the target values

As you can see from the description, there may be duplicate elements in the input array.

Set the value to target.

  • Locate the leftmost occurrence of target in the array. Locate target+1 at the leftmost position in the array.
  • Locate the leftmost occurrence of target in the array. Look for target’s right-most position in the array.

Explain “left” and “right” :

  • The leftmost position appears like this: iterating from index 0, the first position that matches the condition. For example [1,2,2,2,5], the leftmost occurrence of 2 is index 1.
  • The right-most position appears like this: the first position that matches the condition is traversed from the largest index. For example [3,3,3,3,9], the right-most occurrence of 3 is index 3.
Method a

Target, target+1.

func searchRange(nums []int, target int) []int {
    l := len(nums)
    if l == 0 {
        return []int{- 1.- 1}}// Find the left-most position of target
    i, found := searchLeftMost(nums, target)
    if! found {return []int{- 1.- 1}}// Find the left-most position of target+1
    j, _ := searchLeftMost(nums, target+1)
    // It doesn't matter if target+1 is found, j is the position adjacent to the right-most position where I appears.
    // j-1 is still a valid index when j is the length of the array.
    return []int{i,j- 1}}// Search target for the left-most position in nums.
// Return value:
// - The first return value is an index in the range of [0, array length].
// - If found, the index is where target first appears from left to right.
// - If not found, the index is the position where target was inserted in order.
// - The second return value
// - true- find
// -false - Not found
func searchLeftMost(nums []int, target int) (int.bool) {
    var (
        l = len(nums)
        low int
        high = l- 1
    )
    for low <= high {
        mid := low + (high-low)>>1
        v := nums[mid]
        if v >= target {
            // if v is greater than or equal to target, go to the left.
            high = mid- 1
        } else {
            // if v is less than target, go to the right and increase low.
            low = mid+1}}// The value of low ranges from 0 to L.
    // Consider the following cases,
    // [1,3,3, 5], target=3. Here low=1, please use the above loop to deduce their own.
    // [1,3,3, 5], target=-1. Here low=0, because low hasn't changed in the loop above.
    // [1,3,3, 5], target=6. So low is equal to 5, because it keeps going up in the loop.
    // There is no need for low >= 0, because in the loop above, low only stays the same or increases.
    if low < l && nums[low] == target {
        return low, true
    }
    // If low is not a valid index, it is not found.
    return low, false
}
Copy the code
Method 2

Find Target twice. On the basis of the above solution, focus on searchRightMost function.

func searchRange(nums []int, target int) []int {
    l := len(nums)
    if l == 0 {
        return []int{- 1.- 1}
    }
    i, found := searchLeftMost(nums, target)
    if! found {return []int{- 1.- 1}
    }
    j, _ := searchRightMost(nums, target)
    return []int{i,j}
}

func searchLeftMost(nums []int, target int) (int.bool) {
    var (
        l = len(nums)
        low int
        high = l- 1
    )
    for low <= high {
        mid := low + (high-low)>>1
        v := nums[mid]
        if v < target {
            low = mid+1
        } else {
            high = mid- 1}}if low < l && nums[low] == target {
        return low, true
    }
    return low, false
}

func searchRightMost(nums []int, target int) (int.bool) {
    var (
        l = len(nums)
        low int
        high = l- 1
    )
    for low <= high {
        mid := low + (high-low)>>1
        v := nums[mid]
        if v > target {
            // Keep looking to the left, so low stays the same, high decreases.
            high = mid- 1
        } else {
            // Keep looking to the right, so low goes up, high stays the same.
            low = mid+1}}// The value of high is [-1,l).
    // Consider the following cases,
    // [1,3,3, 5], target=3. High =3.
    // [1,3,3, 5], target=-1. So high is minus 1, because high is decreasing all the way up here.
    // [1,3,3, 5], target=6. Here high=4, because high hasn't changed in the loop above.
    // There is no need to say that high < l, because in the above loop, high only stays the same or decreases.
    if high > - 1 && nums[high] == target {
        return high, true
    }
    return high, false
}
Copy the code

The second questionFind a number in a sorted array

This problem is basically the same as the previous one, except that the return value is different, so I won’t repeat it here.