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],找出替换后的数组的给定值 位置
 * */
type TargetValueOfRotateArray struct {
}

func (m *TargetValueOfRotateArray) Method(array []int, target int) int {
	if len(array) == 0 {
		return C.ErrorNum
	}
	left, right, mid := 0, len(array)-1, 0
	for left < right {
		mid = (left + right) / 2
		if array[mid] == target {
			return mid
		}
		// tips 先定位 left和mid的关系，再细分 mid的位置
		if array[mid] > array[left] {
			if array[left] < target && target < array[mid] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else {
			if array[mid] < target && target < array[right] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
	}
	return C.ErrorNum
}

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