问题
通过IP地址可用查找到IP归属地。在百度搜索框里，随便输入一个IP地址，就会看到它的归属地。
这个功能是通过维护一个很大的IP地址库来实现的，地址库中包括IP地址范围和归属地的对应关系。
问题是，如果有12万条这样的IP区间与归属地的对应关系，如何快速定位出一个IP地址的归属地呢？
二分查找的变形
二分查找中最简单的一种情况，是在不存在重复元素的有序数组中，查找值等于给定值的元素。最简单的二分查找比较容易，但是，二分查找的变形问题就没那么好写了。
特别说明：假设要处理的数据是从小到大排列为前提，如果要处理的数据是从大到小排列的，解决思路也是一样的。
几个典型的变形问题
查找第一个值等于给定值的元素
有序数据集合中存在重复的数据，找到第一个值等于给定值的数据。比如，有以下这样一个有序数组，希望找到第一个等于8的数据位置，即下标为5的8.
a[10] 1 3 4 5 6 8 8 8 11 19
0 1 2 3 4 5 6 7 8 9
若用之前的二分查找代码实现，首先拿 8 与区间的中间值 a[4] 比较，8 比 6 大，于是在下标 5 到 9 之间继续查找。下标 5 和 9 的中间位置是下标 7，a[7] 正好等于 8，所以代码就返回了。
尽管 a[7] 等于 8，但它并不是要找的第一个等于 8 的元素，因为第一个值等于 8 的元素是数组下标为 5 的元素。
正确的代码
def binary_search_variant1(arr,ele):
length = len(arr)
low = 0
high = length - 1
while low <= high:
mid = low + ((high-low)>>1)
if arr[mid] > ele:
high = mid -1
elif arr[mid] < ele:
low = mid + 1
else:
if mid == 0 or arr[mid-1] != ele:
return mid
high = mid-1
return -1
分析
重点在于：当 a[mid] = ele 时，该如何处理？如果查找的是任意一个值等于给定值的元素，当 a[mid] 等于要查找的值时，a[mid] 就是要找的元素。但是，求解的是第一个值等于给定值的元素，当 a[mid] 等于要查找的值时，还需要确认一下这个 a[mid] 是不是第一个值等于给定值的元素。
如果 mid 等于 0，那这个元素已经是数组的第一个元素，那它肯定是正确的；如果 mid 不等于 0，但 a[mid] 的前一个元素 a[mid-1] 不等于 ele，那也说明 a[mid] 就是要找的第一个值等于给定值的元素。
如果经过检查之后发现 a[mid] 前面的一个元素 a[mid-1] 也等于 ele，那说明此时的 a[mid] 肯定不是要查找的第一个值等于给定值的元素。那就更新 high=mid-1，因为要找的元素肯定出现在 [low, mid-1] 之间。
查找最后一个值等于给定值的元素
理解上一个变体的做法，对于查找最后一个值等于给定值的元素，就很好做了。
代码
def binary_search_variant2(arr,ele):
length = len(arr)
low = 0
high = length - 1
while low <= high:
mid = low + ((high-low)>>1)
if arr[mid] > ele:
high = mid -1
elif arr[mid] < ele:
low = mid + 1
else:
if mid == (length-1) or arr[mid+1] != ele:
return mid
low = mid+1
return -1
分析
如果 a[mid] 这个元素已经是数组中的最后一个元素了，那它肯定是正确的；如果 [mid] 的后一个元素 a[mid+1] 不等于 ele，那也说明 a[mid] 就是要找的最后一个值等于给定值的元素。
如果经过检查之后，发现 a[mid] 后面的一个元素 a[mid+1] 也等于 ele，那说明当前的这个 a[mid] 并不是最后一个值等于给定值的元素。那就更新 low=mid+1，因为要找的元素肯定出现在 [mid+1, high] 之间。
找第一个大于等于给定值的元素
第三类变形问题。在有序数组中，查找第一个大于等于给定值的元素。
比如，数组中存储的这样一个序列：3，4，6，7，10。如果查找第一个大于等于 5 的元素，那就是 6。
代码
def binary_search_variant3(arr,ele):
length = len(arr)
low = 0
high = length - 1
while low <= high:
mid = low + ((high-low)>>1)
if arr[mid] >= ele:
if mid == 0 or arr[mid-1] < ele:
return mid
high = mid - 1
else:
low = mid + 1
return -1
分析
如果 a[mid] 小于要查找的值 ele，那要查找的值肯定在 [mid+1, high] 之间，所以，更新 low=mid+1。
对于 a[mid] 大于等于给定值 ele 的情况，要确认这个 a[mid] 是不是要找的第一个值大于等于给定值的元素。如果 a[mid] 前面已经没有元素，或者前面一个元素小于要查找的值 ele，那 a[mid] 就是要找的元素。
如果 a[mid-1] 也大于等于要查找的值 ele，那说明要查找的元素在 [low, mid-1] 之间，所以，将 high 更新为 mid-1。
查找最后一个小于等于给定值的元素
查找最后一个小于等于给定值的元素。
比如，数组中存储了这样一组数据：3，5，6，8，9，10。最后一个小于等于 7 的元素就是 6。
代码
def binary_search_variant4(arr,ele):
length = len(arr)
low = 0
high = length - 1
while low <= high:
mid = low + ((high-low)>>1)
if arr[mid] <= ele:
if mid == (length-1) or arr[mid+1] > ele:
return mid
low = mid + 1
else:
high = mid - 1
return -1
解答开篇
如何快速定位出一个 IP 地址的归属地？
如果 IP 区间与归属地的对应关系不经常更新，就可以先预处理这 12 万条数据，让其按照起始 IP 从小到大排序。
IP 地址可以转化为 32 位的整型数。所以，可以将起始地址，按照对应的整型值的大小关系，从小到大进行排序。
然后，这个问题就可以转化为第四种变形问题“在有序数组中，查找最后一个小于等于某个给定值的元素”了。
当要查询某个 IP 归属地时，可以先通过二分查找，找到最后一个起始 IP 小于等于这个 IP 的 IP 区间，然后，检查这个 IP 是否在这个 IP 区间内，如果在，就取出对应的归属地显示；如果不在，就返回未查找到。
Key
凡是用二分查找能解决的问题，绝大部分更倾向于用散列表或者二叉查找树。即便是二分查找在内存使用上更节省，但是毕竟内存如此紧缺的情况并不多。
实际上，求“值等于给定值”的二分查找确实不怎么会被用到，二分查找更适合用在“近似”查找问题，在这类问题上，二分查找的优势更加明显。比如上面的几种变体问题，用其他数据结构，比如散列表、二叉树，就比较难实现了。
变体的二分查找算法写的时候容易因为细节处理不好而产生 Bug，这些容易出错的细节有：终止条件、区间上下界更新方法、返回值选择。