// ++++++++++++++++++++++++++++++++++++++++
// 《零基础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"
	"math/rand"
	"time"
)

type Solution struct {
	values   []int
	maxValue int
}

func NewSolution(w []int) Solution {
	values := []int{}
	current := 0
	for _, v := range w {
		current += v
		values = append(values, current)
	}
	rand.Seed(time.Now().UnixNano())
	return Solution{
		values:   values,
		maxValue: current,
	}
}

func (s *Solution) PickIndex() int {
	num := rand.Intn(s.maxValue)
	return findGreater(s.values, num)
}

// 二分查找较大的值
func findGreater(values []int, num int) int {
	l, r := 0, len(values)-1
	for l <= r {
		m := (l + r) >> 1
		if values[m] > num {
			r = m - 1
		} else {
			l = m + 1
		}
	}
	return l
}

func main() {
	array := []int{1, 2, 9, 20, 31, 45, 63, 70, 100}
	res := NewSolution(array)
	fmt.Println(res.maxValue)
	fmt.Println(res.values)
}

//$ go run interview7-2.go
//341
//[1 3 12 32 63 108 171 241 341]