一道面试题，Ip地址范围找到对应城市

  给一个text file，里面是IP地址的范围，和对应的城市（ex, 192.168.1.0 --- 192.168.1.255,   Boston). 设计一个算法，输入一个具体的IP地址，返回对应的城市。如果IP地址不在任何range之内，返回null。  在一个面经里面看到的题，没有想到什么好方法，求助。

flashstar 发表于 2015-11-16 07:27
建立一个BST，叶子的节点储存 城市和IP地址的边界值，中间的节点只存IP边界值，拿到一个IP地址，按照BST方 ...

不过从简单程度来说还是前面的数组最简单。
建立一个排序数组，里面存 IP边界值和相关的 城市，  然后二分法查找最容易。

建立一个BST，叶子的节点储存 城市和IP地址的边界值，中间的节点只存IP边界值，拿到一个IP地址，按照BST方式搜索，找到2个叶子节点夹住的区间，所在的城市就是对应城市。要考虑一些边界情况。如果BST比较balance, 复杂度是logN

daniel647 发表于 2015-11-9 11:31
问一下lz这是哪个position啊

不清楚啊 我也是看的面经合集里面的一道题。。。这个题要怎么做啊？

请问一下楼主这是哪个公司的面经呢？

水逼一枚 发表于 2015-11-9 09:57
请问一下楼主这是哪个公司的面经呢？

TripAdvisor的，这个要怎么做啊？

oneshot 发表于 2015-11-9 11:27
TripAdvisor的，这个要怎么做啊？

问一下lz这是哪个position啊

我想想
建个数组排序完了二分

3数一组做trie

b tree怎么样