【算法打卡60天】Day14二分查找（下）：如何快速定位IP对应

学习内容：四种常见的二分查找变形问题
1.变体一：查找第一个值等于给定值的元素
2.变体二：查找最后一个值等于给定值的元素
3.变体三：查找第一个大于等于给定值的元素
4.变体四：查找最后一个小于等于给定值的元素

如何快读定位IP对应的省份地址？
答：如果 IP 区间与归属地的对应关系不经常更新，我们可以先预处理这 12 万条数据，让其按照起始 IP 从小到大排序。如何来排序呢？我们知道，IP 地址可以转化为 32 位的整型数。所以，我们可以将起始地址，按照对应的整型值的大小关系，从小到大进行排序。然后，这个问题就可以转化为我刚讲的第四种变形问题“在有序数组中，查找最后一个小于等于某个给定值的元素”了。当我们要查询某个 IP 归属地时，我们可以先通过二分查找，找到最后一个起始 IP 小于等于这个 IP 的 IP 区间，然后，检查这个 IP 是否在这个 IP 区间内，如果在，我们就取出对应的归属地显示；如果不在，就返回未查找到。

今天这4种二分查找，自己需要写一遍，深入理解下问题。自己动手操作过的，印象比较深刻，彻底理解二分查找。
本文参考【极客时间】专栏《数据结构与算法之美》。