hi, what I try to do is: having an sorted array that represents the limits of "squares" of different length, find how many squares "touch" a range, for example it the array a = {0, 9, 18,27, 36, 45, 54, 63, 72, 81, 90} find out how many squares crosses the range 5-47
I have a sketch
package main
import "fmt"
func rangeCells( a, b int, cells []int ) int {
min, max := 0, 0
for i := 0; i < len( cells ) && a > cells[ i ]; i++ { min = i }
for i := 0; i < len( cells ) && b > cells[ i ]; i++ { max = i }
return max - min + 1
}
func main(){
data := [...]struct{
a, b, out int
cells []int
} {
{ 0, 9, 1, []int{ 0, 9, 18, 27, 36, 45, 54, 63, 72, 81, 90 } },
{ 0, 5, 1, []int{ 0, 9, 18, 27, 36, 45, 54, 63, 72, 81, 90 } },
{ 2, 9, 1, []int{ 0, 9, 18, 27, 36, 45, 54, 63, 72, 81, 90 } },
{ 2, 8, 1, []int{ 0, 9, 18, 27, 36, 45, 54, 63, 72, 81, 90 } },
{ 0, 18, 2, []int{ 0, 9, 18, 27, 36, 45, 54, 63, 72, 81, 90 } },
{ 9, 18, 2, []int{ 0, 9, 18, 27, 36, 45, 54, 63, 72, 81, 90 } }, // [edit] error must be 1, no 2
{ 7, 18, 2, []int{ 0, 9, 18, 27, 36, 45, 54, 63, 72, 81, 90 } },
{ 5, 45, 5, []int{ 0, 9, 18, 27, 36, 45, 54, 63, 72, 81, 90 } },
{ 5, 46, 6, []int{ 0, 9, 18, 27, 36, 45, 54, 63, 72, 81, 90 } },
{ 15, 90, 9, []int{ 0, 9, 18, 27, 36, 45, 54, 63, 72, 81, 90 } },
}
for _, d := range data {
if r := rangeCells( d.a, d.b, d.cells ); r != d.out {
fmt.Printf( "Error rangeCells( %d, %d, %v )\n\tresult %d != %d expected", d.a, d.b, d.cells, r, d.out )
}
}
}
although the arrangements would be really small and sequential queries could shorten the arrangement with the boxes on each call, I think there is a better way than how is this raised, any ideas?
playground > https://play.golang.org/p/AvADZEpnlO
评论：
epiris:
If the list is sorted you could use sort.SearchInts to binary search the start and end values. Keep in mind your implementation is probably fine until you hit hundreds of items, for end range search make sure to give the call to SearchInts a slice from the previously found start boundary to prevent needless scanning of those elements.
