package main

func findPeakElement(nums []int) int { // Return peak index
	length := len(nums)
	if length == 1 {
		return 0
	}
	beg, end := 0, length-1 // Index is important
	mid := (beg + end) / 2
	for beg < end {
		midLeft := (beg + mid) / 2
		if nums[midLeft] > nums[mid] {
			end = mid
			mid = midLeft
			continue
		}
		midRight := (mid + end) / 2
		if nums[midRight] > nums[mid] {
			beg = mid
			mid = midRight
			continue
		}
		if mid == midRight {
			break // Avoid infinity loop
		}
		beg = midLeft
		end = midRight
	}
	if end > length-1 || nums[mid] > nums[end] {
		return mid
	}
	return end
}

// func main() {
// 	println(findPeakElement([]int{
// 		1, 2, 1, 3, 5, 6, 4}))
// 	println(findPeakElement([]int{
// 		1, 2}))
// 	println(findPeakElement([]int{
// 		1, 2, 1, 3, 2, 1}))
// 	println(findPeakElement([]int{
// 		1, 2, 3, 1, 2, 1}))
// 	println(findPeakElement([]int{
// 		-67, -60, 78, 31, -24, -78, -89, 14, -18, 39, //   0~9
// 		-4, 60, -33, 77, 48, 22, 88, -40, -83, 25, //     10~19
// 		-55, 68, 61, -72, -77, 8, -11, 90, -75, -86, //   20~29
// 		-85, -66, -79, 26, 30, 32, 81, 27, 12, 86, //     30~39
// 		23, -41, 20, -58, 57, 10, 54, -27, -63, -94})) // 40~49
// }