forked from TheAlgorithms/Go
-
Notifications
You must be signed in to change notification settings - Fork 0
/
ternary.go
40 lines (37 loc) · 1.16 KB
/
ternary.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package search
import (
"fmt"
"math"
)
// TernaryMax is a function to search for maximum value of a uni-modal function `f`
// in the interval [a, b]. a and b should be finit numbers
func TernaryMax(a, b, epsilon float64, f func(x float64) float64) (float64, error) {
if a == math.Inf(-1) || b == math.Inf(1) {
return -1, fmt.Errorf("interval boundaries should be finite numbers")
}
if math.Abs(a-b) <= epsilon {
return f((a + b) / 2), nil
}
left := (2*a + b) / 3
right := (a + 2*b) / 3
if f(left) < f(right) {
return TernaryMax(left, b, epsilon, f)
}
return TernaryMax(a, right, epsilon, f)
}
// TernaryMin is a function to search for minimum value of a uni-modal function `f`
// in the interval [a, b]. a and b should be finit numbers.
func TernaryMin(a, b, epsilon float64, f func(x float64) float64) (float64, error) {
if a == math.Inf(-1) || b == math.Inf(1) {
return -1, fmt.Errorf("interval boundaries should be finite numbers")
}
if math.Abs(a-b) <= epsilon {
return f((a + b) / 2), nil
}
left := (2*a + b) / 3
right := (a + 2*b) / 3
if f(left) > f(right) {
return TernaryMin(left, b, epsilon, f)
}
return TernaryMin(a, right, epsilon, f)
}