package main

// important
func searchRange(nums []int, target int) []int {
	beg, end := 0, len(nums)-1
	res := []int{-1, -1}
	// search left
	for beg < end {
		mid := (beg + end) / 2
		if target > nums[mid] {
			beg = mid + 1
		} else {
			end = mid
		}
	}
	if end == -1 || nums[beg] != target {
		return res
	}
	res[0] = beg
	end = len(nums) - 1
	// search right
	for beg < end {
		mid := (beg+end)/2 + 1 // notice: if mid == i, will loop forever
		if target < nums[mid] {
			end = mid - 1
		} else {
			beg = mid
		}
	}
	res[1] = end
	return res
}

/* func main() {
	a1 := []int{1, 2, 3, 4, 4, 4, 5, 6, 7, 8, 9, 10}
	fmt.Println(searchRange(a1, 4))
	fmt.Println(searchRange(a1, 5))
	fmt.Println(searchRange(a1, 11))
	fmt.Println(searchRange(a1, 1))
	fmt.Println(searchRange(a1, 10))
	a2 := []int{5, 7, 7, 8, 8, 10}
	fmt.Println(searchRange(a2, 8))
	fmt.Println(searchRange([]int{}, 9))
} */