// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

func firstBadVersion(n int) int {
	fibMMinus2 := 0
	fibMMinus1 := 1
	fibM := fibMMinus1 + fibMMinus2

	//找到大于或等于 n 的最小斐波那契数
	for fibM < n {
		fibMMinus2 = fibMMinus1
		fibMMinus1 = fibM
		fibM = fibMMinus1 + fibMMinus2
	}

	index := -1
	//使用斐波那契数列执行搜索
	for fibM > 1 {
		//计算要检查的指标
		i := min(index+fibMMinus2, n-1)

		//如果当前版本好，则丢弃左侧部分并向右移动
		if !isBadVersion(i) {
			fibM = fibMMinus1
			fibMMinus1 = fibMMinus2
			fibMMinus2 = fibM - fibMMinus1
			index = i
		} else {
			//如果当前版本不好，则丢弃右边的部分并向左移动
			fibM = fibMMinus2
			fibMMinus1 = fibMMinus1 - fibMMinus2
			fibMMinus2 = fibM - fibMMinus1
		}
	}

	//查看最后一个版本
	if fibMMinus1 > 0 && index < (n-1) && isBadVersion(index+1) {
		return index + 1
	}

	return n
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func isBadVersion(version int) bool {
	return version >= 5
}

func main() {
	n := 8
	firstBad := firstBadVersion(n)
	fmt.Printf("第1个坏版本是：%v", firstBad)
}

//$ go run interview7-7.go
//第1个坏版本是：5