如何在非常大的结构中找到范围内的ip

Question

我有一个像下面这样的结构，大约有 10 万个。我想遍历它并检查 IP 地址是否在范围内。我目前的代码：type Users struct {    Id        string    Descr     string    IpStart   string    IpEnd     string}var users []*Usersfunc LookUpIP(IpAddress string) (string, string) {    iptocheck := net.ParseIP(IpAddress)    for _, elem := range users {        if bytes.Compare(iptocheck, elem.IpStart) >= 0 && bytes.Compare(iptocheck, elem.IpEnd) <= 0 {            fmt.Printf("%v is between %v and %v\n", IpAddress, elem.IpStart, elem.IpEnd)            return elem.Id, elem.Descr         }    }    return "0", "null"}以上对大约 40k 的整数工作正常，但超过它会变慢。有没有更快的方法来确定一个 ip 地址是否在我的结构内的范围内？更新：现在只解析一次 IP 并将其存储为结构中的数字

Answer 1

我看到有两个简单的步骤。

1. 进行一次解析并将 IP 地址存储为单个数字。

2. 按范围的开头对范围进行排序并使用二分搜索。

Answer 2

作为@Grzegorz Żur建议使用二分搜索来减少搜索时间的补充，这里是一个二分搜索实现。

但首先什么是二分搜索？二分搜索将一系列值分成两半，并继续缩小搜索范围，直到找到未知值。它是“分而治之”算法的经典示例。

该算法返回与给定值相等的某个元素的索引（如果有多个这样的元素，它返回任意一个）。当未找到元素时，也可以为其返回“插入点”（如果将值插入数组，则该值将具有的索引）。

递归方法

func binarySearch(a []float64, value float64, low int, high int) int {

    if high < low {

        return -1

    }

    mid := (low + high) / 2 // calculate the mean of two values

    if a[mid] > value {

        return binarySearch(a, value, low, mid-1)

    } else if a[mid] < value {

        return binarySearch(a, value, mid+1, high)

    }

    return mid

}

迭代法

func binarySearch(a []float64, value float64) int {

    low := 0

    high := len(a) - 1

    for low <= high {

        mid := (low + high) / 2

        if a[mid] > value {

            high = mid - 1

        } else if a[mid] < value {

            low = mid + 1

        } else {

            return mid

        }

    }

    return -1

}

但是，如果您查看sort 包，您会发现已经实现了基于二进制搜索的排序算法。所以这可能是最好的选择。