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

题目描述

题解思路

这题让我们求目标值的左边界和右边界，我们可以采用二分查找搜索有序数组内大于等于目标值的最左边的下标

然后我们只需要在有序数组查找一下大于等于target的最左边下标

• 如果该下标越界或者下标对应的值不等于target，则说明有序数组中不存在target，直接返回没找到target的第一个位置
• 如果找到target的第一个位置，我们查找大于等于target + 1的最左边下标，然后该下标减一就是target的最后一个位置，然后返回结果

题解代码

func searchRange(nums []int, target int) []int {
    if len(nums) == 0 {
        return []int{-1, -1}
    }
    var binarySearch func(target int) int
    binarySearch = func(target int) int {
        l, r := 0, len(nums) - 1
        for l <= r {
            m := (l + r) >> 1
            if nums[m] < target {
                l = m + 1
            } else {
                r = m - 1
            }
        }

        return l
    }

    l := binarySearch(target)
    if l == len(nums) || nums[l] != target {
        return []int{-1, -1}
    }

    return []int{l, binarySearch(target + 1) - 1}
}

题目链接

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/