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

One minute read
LeetCode
面试 • 算法 • 数据结构

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

题目

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

你的算法时间复杂度必须是 O(log n) 级别。

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

示例 1:

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

示例 2:

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

直接二分法，找到pos位置

然后pos向左、向右遍历找到边界

解答

func searchRange(nums []int, target int) []int {
    if len(nums) == 0 {
        return []int{-1, -1}
    }
    
    low, high, pos := 0, len(nums)-1, 0
    
    // 二分法
    for low <= high {
        pos = low + (high-low)>>2
        if nums[pos] == target {
            break
        }
        if target < nums[pos] {
            high = pos-1
        } else {
            low = pos+1
        }
    }
       
    if target != nums[pos] {
        return []int{-1, -1}
    }
    
    ret := []int{-1, -1}
    for i := pos; i >= 0; i-- {
        if nums[i] == target {
            ret[0] = i
        } else {
            break
        }
    }
    
    for i := pos; i < len(nums); i++ {
        if nums[i] == target {
            ret[1] = i
        } else {
            break
        }
    }
    return ret
}

// 执行用时 :8 ms, 在所有 Go 提交中击败了94.39%的用户
// 内存消耗 :4.1 MB, 在所有 Go 提交中击败了100.00%的用户

分享：