LeetCode 0034.查找元素位置

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

题目描述

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

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

示例 1：

1
2


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

示例 2：

1
2


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

示例 3：

1
2


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

思路

题目要求

在升序数组中查找目标元素的索引区间
若未找到目标元素，则返回[-1, -1]

在升序数组中查找目标元素，考虑使用二分查找法。但需要对二分法做出适当改变。

由于目标元素在数组中可能重复，所以使用二分法时需要在找到目标元素后，继续再向左和向右寻找左边界和右边界。

由于数组是升序的，所以重复元素在数组中也一定是连续的。

寻找左边界就是寻找第一个大于等于目标元素的元素的索引，寻找有边界就是寻找第一个大于目标元素的元素的索引。

注意

寻找左边界：当找到目标元素后，判断当前元素nums[mid]，若是mid=0或nums[mid-1] < target，则无需继续向左寻找，左边界就是当前元素的索引mid。反之，执行right = mid - 1，继续左区间中寻找左边界。
寻找右边界：当找到目标元素后，判断当前元素nums[mid]，若是mid=len(nums)-1或nums[mid+1] > target，则无需继续向左寻找，左边界就是当前元素的索引mid。反之，执行left = mid + 1，继续右区间中寻找右边界。

代码

Go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


// 找左边界
func getLeftBorder(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] < target {
            left = mid + 1
        } else if nums[mid] > target {
            right = mid - 1
        } else if nums[mid] == target && (mid == 0 || nums[mid-1] < target) {
            return mid
        } else {
            right = mid - 1
        }
    }
    return -1
}

//找右边界
func getRightBorder(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] < target {
            left = mid + 1
        } else if nums[mid] > target {
            right = mid - 1
        } else if nums[mid] == target && (mid == len(nums)-1 || nums[mid+1] > target) {
            return mid
        } else {
            left = mid + 1
        }
    }
    return -1
}

func searchRange(nums []int, target int) []int {
    leftBorder := getLeftBorder(nums, target)
    rightBorder := getRightBorder(nums, target)
    return []int{leftBorder, rightBorder}
}

Link

GitHub