条件：
给出一个文件，其中每行一个IP段(IPv4，其实IPv6类似，只是规模剧增)及其对应的信息(例如物理地址信息)，内容及格式为：
<start_IP> <end_IP> <country> <province/state> <city> <other_info>
内容说明：
1. <start_IP> <end_IP>都为包含状态，即[<start_IP>, <end_IP>]
2. 各IP段不重合
3. IP段有空洞，即有些IP不能找到对应段
问题：
给出一个IP，请实现算法返回其对应的<country> <province/state> <city> <other_info>等信息
算法一：
扩展每个IP段，构造每个IP与其对应<country> <province/state> <city> <other_info>信息的结构，以IP作key读入内存
优点：简单易实现
缺点：占用内容过大
算法二：
扩展每个IP段，构造每个IP与其对应<country> <province/state> <city> <other_info>信息的数据，以IP作key写入数据库
优点：简单易实现
缺点：需要额外的数据库服务，使用频繁时性能不高
算法三：
近似查找。此方法有两个关键点：
1. 查找过程中需要比较IP的大小，因此需要实现IP的比较。也有两种实现：1) 实现一个IP的比较器 2) 把IP转换为数字：IP看作是一个4位的数字，每位之间进制256，例如10.13.183.72=10 * 256^3 + 13 * 256^2 + 183 * 256^1 + 72 * 256 ^0，这样需把给定的IP和每一段IP的<start_IP>, <end_IP>都做相同转换，便于比较
代码：
long num = 16777216L * Long.parseLong(ips[0]) + 65536L
* Long.parseLong(ips[1]) + 256 * Long.parseLong(ips[2])
+ Long.parseLong(ips[3]); return num;
或更快速的移位实现：
long num = 0;
for (int i = 0; i < ips.length; i++) {
num += Long.parseLong(ips[i]) << (8 * (ips.length - 1 - i));
}
return num;
2. 查找算法需要改进，因为是查找一个值所属的范围，并非直接命中式的查找。以折半查找为例，改造如下：
1) 将IP段的<start_IP>转换为数字，构造查询有序数组A。以每段的<end_IP>构造另一个备查数组B，同一段的<start_IP> <end_IP>在各自数组中索引一致。
2) 命中算法改为近似算法，更精确的叫作向下最近算法，基于数组A执行折半查找
3) 以A中的索引位查找数组B，确认目标IP在对应段中。防止误查本应在空洞段中的IP
#数组A
private List<Long> startIPNOsList = new ArrayList<Long>();
#数组B
private List<Long> endIPNOsList = new ArrayList<Long>();
#对应信息数组C
private List<Address> addressList = new ArrayList<Address>(); //...构造上述数组 /**
* 实现查找
*/
public Address detect(String ip) {
long ipNO = IPv4Util.convertIP2Long(ip); if (ipNO > 0) {
int idx = containBinSearch(ipNO, 0, startIPNOsList.size() - 1);
if (idx > 0 && ipNO <= endIPNOsList.get(idx)) {
return addressList.get(idx);
}
}
short zero = 0;
return new Address(zero, zero, zero);
} /**
* 如果arr[i] <= target && arr[i + 1] > target，则返回i
* @param target 查找目标
* @param low
* @param high
* @return
*/
private int containBinSearch(long target, int low, int high) {
//表示没查到
if (high < low) {
return -1;
} int mid = (low + high) / 2;
if (mid == startIPNOsList.size() - 1) {
return mid;
} if (startIPNOsList.get(mid) > target) {
return containBinSearch(target, low, mid - 1);
} else if (startIPNOsList.get(mid + 1) <= target) {
return containBinSearch(target, mid + 1, high);
} else {
return mid;
}
}
优点：占用内存小，查询速度不错
缺点：实现稍复杂
算法四：
Trie树实现。
“Trie树即字典树。
具体实现：扩展每个IP段，将每个IP加入Trie树。每个ip位构造一个节点，每个叶子节点包含<country> <province/state> <city> <other_info>等信息，最后构造一个5层的trie树。
优点：查询速度快，实现较简单
缺点：占用内存超大
算法五：
近似trie树查找。基本结构与算法四相同，查找算法需改进，构造树时需在叶节点中包含<end_ip>。
实现：
对于IP第1-4位，分别在trie树第2-5层节点应用如下逻辑
1 查找当前层中最大的不大于当前位的节点
a) 如果当前节点是叶节点，验证目标IP是否大于<end_ip>：大于返回空，否则返回对应<country>等信息
b) 如果查找到的节点值等于当前位的值，向下一层重复此逻辑
c) 如果查找到的节点值小于当前位的值，返回本节点最大值的叶节点
2 如果查找不到，本节点的父节点值 -1，本节点及其各子节点置为255，返回上一层重复此逻辑
优点：速度快，较算法4占内存小
确定：查找算法复杂，内存占用仍旧很大