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

1. 题目描述

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

2. 思路

1. 二分查找上界下界
2. 先二分在上下界

3. 实现

3.1. 二分查找上界下界

package main

func searchRange(nums []int, target int) []int {

	if len(nums) == 0 {
		return []int{-1, -1}
	}

	if target > nums[len(nums)-1] || target < nums[0] {
		return []int{-1, -1}
	}

	low := getLower(nums, target)
	high := getHigher(nums, target)

	if low == -1 {
		return []int{-1, -1}
	}

	return []int{low, high}

}

//>
func getHigher(nums []int, target int) int {
	left := 0
	right := len(nums) - 1
	for left < right {
		mid := left + (right-left+1)>>1
		if nums[mid] > target {
			right = mid - 1
		} else if nums[mid] == target {
			left = mid
		} else {
			left = mid + 1
		}
	}

	return left
}

//<=
func getLower(nums []int, target int) int {

	left := 0
	right := len(nums) - 1
	for left < right {
		mid := left + (right-left)>>1
		if nums[mid] > target {
			right = mid - 1
		} else if nums[mid] < target {
			left = mid + 1
		} else {
			right = mid
		}
	}

	if nums[left] == target {
		return left
	}
	return -1

}

3.2. 先二分在上下界

func searchRange(nums []int, target int) []int {
    index := search(nums, target)
    if index == -1 {
        return []int{-1, -1}
    }
    first := searchFirst(nums, target)
    last := searchLast(nums, target)
    return []int{first, last}
}

func searchLast(nums []int, target int) int {
    left := 0
    right := len(nums)-1
    res := -1
    for left <= right {
        mid := left+(right-left)/2
        if nums[mid] == target {
            left = mid+1////这一行注意，不是mid而且多了res
            res = mid
        }else if nums[mid] < target {
            left = mid+1
        }else {
            right = mid -1
        }
    }
    return res
}

func searchFirst(nums []int, target int) int {
    left := 0
    right := len(nums)-1
    res := -1
    for left <= right {
        mid := left+(right-left)/2
        if nums[mid] == target {
            right = mid-1//这一行注意，不是mid而且多了res
            res = mid
        }else if nums[mid] < target {
            left = mid+1
        }else {
            right = mid -1
        }
    }
    return res
}

func search(nums []int, target int) int {
    left := 0
    right := len(nums)-1
    for left <= right {
        mid := left+(right-left)/2
        if nums[mid] == target {
            return mid
        }else if nums[mid] < target {
            left = mid+1
        }else {
            right = mid -1
        }
    }
    return -1
}

4. 参考

• 「代码随想录」带你学透二分法！34.【朴实无华的二分查找】咱们一步一步来 - 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
• 易懂 - 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）