2 ms·
Nice to see that the Go gets it right: func Search(n int, f func(int) bool) int { // Define f(-1) == false and f(n) == true.
by jbarham 15y ago
Nice to see that the Go gets it right:
func Search(n int, f func(int) bool) int {
// Define f(-1) == false and f(n) == true.
// Invariant: f(i-1) == false, f(j) == true.
i, j := 0, n
for i < j {
h := i + (j-i)/2 // avoid overflow when computing h
// i ≤ h < j
if !f(h) {
i = h + 1 // preserves f(i-1) == false
} else {
j = h // preserves f(j) == true
}
}
// i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i.
return i
}
http://code.google.com/p/go/source/browse/src/pkg/sort/search.go?name=weekly.2012-01-27#57 http://code.google.com/p/go/source/browse/src/pkg/sort/searc...
- nknight 15y agoI expect at least one of the Go authors was well aware of this very incident (the Java breakage), it was fairly well publicized before Go ever saw the light of day.