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

输入：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 {
	if len(nums) == 0 {
		return []int{-1, -1}
	}
  //找到头
	start := findFirst(nums, target)
	if start == -1 {
		return []int{-1, -1}
	}
  //找到尾
	end := findLast(nums, target)
	return []int{start, end}
}

func findFirst(nums []int, target int) int {
	start, end := 0, len(nums)-1
	for start < end {
		mid := (start + end) / 2
		if nums[mid] > target {
			end = mid - 1
		} else if nums[mid] == target {
			end = mid
		} else {
			start = mid + 1
		}
	}
  //此处防止数组第一个数是 target ，所以校验下是否相等
	if nums[start] == target {
		return start
	}
	return -1
}

func findLast(nums []int, target int) int {
	start, end := 0, len(nums)-1
	for start < end {
    //此处注意,为了防止 start=mid<end 导致死循环的问题
		mid := (start + end + 1) / 2
		if nums[mid] > target {
			end = mid - 1
		} else if nums[mid] == target {
			start = mid
		} else {
			start = mid + 1
		}
	}
	return end
}