请教比较高效的解决方法
一个映射文件中存了ip地址区间和城市名称,形如:
10.0.0.1 10.0.1.27 北京
10.0.2.1 10.0.2.27 北京
201.0.1.12 201.0.2.124 上海
给你一个ip地址,获取城市名称
[解决办法]
将IP地址转为32位整数
于是问题转为 (l,r,c) (l,r):IP 区间,c:城市
定义结构体S(l,r,c)
对所有的信息按照S.l从小到大排序
对于给定的ip x
在排序后的数组中,lower_bound 二分查找第一个S.l>=的结构
如果 存在这个结构 且 x在所给区间内。。。于是就得到了城市名称
否则就不存在包含此ip的区间。
不考虑区间有重叠的情况