昨天朋友面试给我发了一个问题：
给一个text file，里面是IP地址的范围，和对应的城市（ex, 192.168.1.0 --- 192.168.1.255, Boston). 设计一个算法，输入一个具体的IP地址，返回对应的城市。如果IP地址不在任何range之内，返回null。
有如下几个思路：
1. 因为ip地址是有序的，且又都是整数，自然能想到的是把数据存到数组里，然后进行二分查找
2. 也可以建立二叉排序树，叶子节点存储ip地址和边界值，中间节点只存ip地址的边界值，拿到一个IP地址，按照BST方式搜索，找到2个叶子节点夹住的区间，所在的城市就是对应城市。要考虑一些边界情况。如果BST比较balance, 复杂度是logN
3. 利用hash（海量数据查找，速度，各种都是屡试不爽），但关键要看如何散列
如果数据量大的话，不妨用hash散列成n个block，对每个block用有序数组存储，使用二分查找。最后再对n个block进行归并排序。
ps：也有人提到线段树这种数据结构。因为没有接触过，而且说是擅长处理连续值，所以查了一些资料，我们来学习一下。
转自博客园：http://www.cnblogs.com/TenosDoIt/p/3453089.html
线段树，类似区间树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，它基本能保持每个操作的复杂度为O(logn)。
线段树的每个节点表示一个区间，子节点则分别表示父节点的左右半区间，例如父亲的区间是[a,b]，那么(c=(a+b)/2)左儿子的区间是[a,c]，右儿子的区间是[c+1,b]。
下面从一个例子来理解线段树
问题描述如下:从数组arr[0...n-1]中查找某个数组某个区间内的最小值，其中数组大小固定，但是数组中的元素的值可以随时更新。
对这个问题一个简单的解法是：遍历数组区间找到最小值，时间复杂度是O(n),额外的空间复杂度O(1)。当数据量特别大，而查询操作很频繁的时候，耗时可能会不满足需求。
另一种解法：使用一个二维数组来保存提前计算好的区间[i,j]内的最小值，那么预处理时间为O(n^2)，查询耗时O(1), 但是需要额外的O(n^2)空间，当数据量很大时，这个空间消耗是庞大的，而且当改变了数组中的某一个值时，更新二维数组中的最小值也很麻烦。（不适合值经常变动的情况）
我们可以用线段树来解决这个问题：预处理耗时O(n)，查询、更新操作O(logn)，需要额外的空间O(n)。根据这个问题我们构造如下的二叉树
-- 叶子节点是原始组数arr中的元素
--- 非叶子节点代表它的所有子孙叶子节点所在区间的最小值
例如对于数组[2, 5, 1, 4, 9, 3]可以构造如下的二叉树（背景为白色表示叶子节点，非叶子节点的值是其对应数组区间内的最小值，例如根节点表示数组区间arr[0...5]内的最小值是1）：
由此可见，线段树适合查找某一区间的最小值，并不适合上述的查找。
