首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

请问比较高效的解决办法

2012-12-26 
请教比较高效的解决方法一个映射文件中存了ip地址区间和城市名称,形如:10.0.0.1 10.0.1.27 北京10.0.2.1 1

请教比较高效的解决方法
一个映射文件中存了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的区间。

不考虑区间有重叠的情况

热点排行