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

题目描述

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

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

说明

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

示例

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

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

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

二分查找

通过二分查找找到目标数字在数组中的下标，然后向该下标左右两边搜索

func searchRange(nums []int, target int) []int {
	var i, j int
	targetIndex := searchIndex(nums, 0, len(nums)-1, target)
	if targetIndex == -1 {
		return []int{-1, -1}
	}
	for j = targetIndex; j < len(nums) && nums[j] == target; j++ {
	}
	for i = targetIndex; i >= 0 && nums[i] == target; i-- {
	}
	return []int{i + 1, j - 1}
}

func searchIndex(nums []int, i, j, target int) int {
	index := (i + j) / 2
	if nums[index] == target && i < j {
		return index
	} else if nums[index] > target && i < j {
		j = index
	} else if nums[index] < target && i < j {
		i = index + 1
	} else {
		return -1
	}
	return searchIndex(nums, i, j, target)
}

本地测试

package main

import (
	"fmt"
)

func main() {
	fmt.Println("ans is : ", searchRange([]int{5, 7, 7, 8, 8, 10}, 8))
	fmt.Println("ans is : ", searchRange([]int{5, 7, 7, 8, 8, 10}, 6))
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array