LeetCode-34. 在排序数组中查找元素的第一个和最后一个位置

二分查找#

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

1
输入：nums = [5,7,7,8,8,10], target = 8
2
输出：[3,4]

示例 2：

1
输入：nums = [5,7,7,8,8,10], target = 6
2
输出：[-1,-1]

示例 3：

1
输入：nums = [], target = 0
2
输出：[-1,-1]

思路

这题与前面只找一个数不同，这里需要寻找到第一个和最后一个数

其实由于for left <= right的循环结构，具备不断查找的功能，之前只寻找一个数的问题局限了我们的思维，只需要在找到target后，继续执行找到左和右边界即可

所以，我们只需要执行两次二分查找即可

1
func searchRange(nums []int, target int) []int {
2
    first := findBound(nums, target, true)
3
    if first == -1 {
4
        return []int{-1, -1}
5
    }
6

7
    last := findBound(nums, target, false)
8

9
    return []int{first, last}
10
}
11

12
func findBound (nums []int, target int , isFirst bool) int {
13
    left, right := 0, len(nums)-1
14
    bound := -1
15

16
    for left <= right {
17
        mid := left + (right - left)/2
18

19
        if nums[mid] == target {
20
            bound = mid
21
            if isFirst {
22
                right = mid - 1
23
            }else {
24
                left = mid + 1
25
            }
26
        }else if nums[mid] < target {
27
            left = mid + 1
28
        }else {
29
            right = mid - 1
30
        }
31
    }
32
    return bound
33
}

时间复杂度为O(n)的思路

很直接的在查到对应的值后，向左和右用循环找到初始和最后的位置，但时间复杂度为O(n)与题目要求的O(log n) 不符

1
func searchRange(nums []int, target int) []int {
2
    if len(nums) == 0 {
3
        return []int{-1, -1}
4
    }
5

6
    left, right := 0, len(nums)-1
7
    var mid int
8

9
    for left <= right {
10
        mid = left + (right - left)/2
11

12
        if nums[mid] == target {
13
            ans := mid
14
            for mid-1 >= 0 && nums[mid-1] == target {
15
                mid--
16
            }
17
            for ans+1 < len(nums) && nums[ans+1] == target {
18
                ans++
19
            }
20
            return []int{mid, ans}
21
        }else if nums[mid] < target {
22
            left = mid + 1
23
        }else {
24
            right = mid - 1
25
        }
26
    }
27
    return []int{-1, -1}
28
}