package bisection

import C "gitee.com/ljfirst/algo-go-sdk/common/constant"

/**
 * @author ljfirst
 * @version V1.0
 * @date 2023/7/10 00:14
 * @author-Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 求有序数组旋转后的极值(最大值、最小值)
 * 一个有序递增数组，比如[1,2,3,4,5,6,7],后面部分被替换到前面，比如[5,6,7,1,2,3,4],找出替换后的数组的最大值
 * 一个有序递增数组，比如[1,2,3,4,5,6,7],后面部分被替换到前面，比如[5,6,7,1,2,3,4],找出替换后的数组的最小值
 * */
type ExtremeValueOfRotateArray struct {
}

// attention : 1、找最大值，需要对比的值是 array[left]，找最小值，需要对比的值是 array[right]
//             2、对比结束的 else ，即相等的时候，是需要return的
func (m *ExtremeValueOfRotateArray) Method(array []int, getBigger bool) int {
	if len(array) == 0 {
		return C.ErrorNum
	}
	left, right := 0, len(array)-1
	for left < right {
		mid := (left + right) / 2
		if getBigger {
			if array[mid] < array[left] {
				right = mid - 1
			} else if array[mid] > array[left] {
				left = mid
			} else {
				return array[mid]
			}
		} else {
			if array[mid] < array[right] {
				right = mid
			} else if array[mid] > array[right] {
				left = mid + 1
			} else {
				return array[mid]
			}
		}
	}
	return array[left]
}

func (m *ExtremeValueOfRotateArray) GetAttribute() *C.Attribute {
	return &C.Attribute{
		Tags: []string{C.Bisection},
		Desc: &C.Desc{
			Name:   "ExtremeValueOfRotateArray",
			NameCn: "有序数组旋转后的极值(最大值、最小值)",
			Example: map[int]string{
				1: "一个有序递增数组，比如[1,2,3,4,5,6,7],4后面部分被替换到前面，比如[5,6,7,1,2,3,4],找出替换后的数组的最大值",
				2: "一个有序递增数组，比如[1,2,3,4,5,6,7],4后面部分被替换到前面，比如[5,6,7,1,2,3,4],找出替换后的数组的最小值",
			},
		},
	}
}