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

进行两次二分查找

时间复杂度：O(logN)
空间复杂度：O(1)

// 手写二分查找
func searchRange(nums []int, target int) []int {
    if len(nums) == 0 {
        return []int{-1, -1}
    }

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

    if nums[right] != target {
        ans = []int{-1, -1}
        return ans
    } else {
        ans = append(ans, right)
    }

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

    if nums[right] == target {
        ans = append(ans, right)
    } else {
        ans = append(ans, ans[0])
    }

    return ans

}

// 使用标准库

func searchRange(nums []int, target int) []int {
	leftmost := sort.SearchInts(nums, target)
	if leftmost == len(nums) || nums[leftmost] != target {
		// 没有找到target
		return []int{-1, -1}
	}

	// nums中至少有一个target
	rightmost := sort.SearchInts(nums, target + 1) - 1
	return []int{leftmost, rightmost}
}