Go offers the func Search(n int, f func(int) bool) int
function that returns the lowest n at which f(n) is true.
Here's the complete function with comments:
// Search uses binary search to find and return the smallest index i
// in [0, n) at which f(i) is true, assuming that on the range [0, n),
// f(i) == true implies f(i+1) == true. That is, Search requires that
// f is false for some (possibly empty) prefix of the input range [0, n)
// and then true for the (possibly empty) remainder; Search returns
// the first true index. If there is no such index, Search returns n.
// (Note that the "not found" return value is not -1 as in, for instance,
// strings.Index.)
// Search calls f(i) only for i in the range [0, n).
//
// A common use of Search is to find the index i for a value x in
// a sorted, indexable data structure such as an array or slice.
// In this case, the argument f, typically a closure, captures the value
// to be searched for, and how the data structure is indexed and
// ordered.
//
// For instance, given a slice data sorted in ascending order,
// the call Search(len(data), func(i int) bool { return data[i] >= 23 })
// returns the smallest index i such that data[i] >= 23. If the caller
// wants to find whether 23 is in the slice, it must test data[i] == 23
// separately.
//
// Searching data sorted in descending order would use the <=
// operator instead of the >= operator.
//
// To complete the example above, the following code tries to find the value
// x in an integer slice data sorted in ascending order:
//
// x := 23
// i := sort.Search(len(data), func(i int) bool { return data[i] >= x })
// if i < len(data) && data[i] == x {
// // x is present at data[i]
// } else {
// // x is not present in data,
// // but i is the index where it would be inserted.
// }
//
// As a more whimsical example, this program guesses your number:
//
// func GuessingGame() {
// var s string
// fmt.Printf("Pick an integer from 0 to 100.
")
// answer := sort.Search(100, func(i int) bool {
// fmt.Printf("Is your number <= %d? ", i)
// fmt.Scanf("%s", &s)
// return s != "" && s[0] == 'y'
// })
// fmt.Printf("Your number is %d.
", answer)
// }
//
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
}
I could simply split n in k-slices where k is the amount of worker I want and then, compute the k searches of n/k elements. Finally, I would take the minimum of the ns returned by my workers.
The thing is, if for a given k (processing the entries [kn/k, kn/k+n/k[) f(n) is true, then, it serves no purpose to keep computing higher rank of k as they would return higher values for n and we look for the minimum.
What would be the idiomatic go way to create cancellable jobs for such a problem?
Thanks,