16 | 二分查找（下）：如何快速定位IP对应的省份地址？

有三种方法查找循环有序数组 一、 1. 找到分界下标，分成两个有序数组 2. 判断目标值在哪个有序数据范围内，做二分查找 二、 1. 找到最大值的下标 x; 2. 所有元素下标 +x 偏移，超过数组范围值的取模; 3. 利用偏移后的下标做二分查找； 4. 如果找到目标下标，再作 -x 偏移，就是目标值实际下标。 两种情况最高时耗都在查找分界点上，所以时间复杂度是 O(N）。 复杂度有点高，能否优化呢？ 三、 我们发现循环数组存在一个性质：以数组中间点为分区，会将数组分成一个有序数组和一个循环有序数组。 如果首元素小于 mid，说明前半部分是有序的，后半部分是循环有序数组； 如果首元素大于 mid，说明后半部分是有序的，前半部分是循环有序的数组； 如果目标元素在有序数组范围中，使用二分查找； 如果目标元素在循环有序数组中，设定数组边界后，使用以上方法继续查找。 时间复杂度为 O(logN)。

第一段代码有漏洞，且不说int能不能表示数组的下标问题，毕竟这个数组能越界说明相当庞大了； 主要问题在于，如果我给定的数大于任何一个数组元素，low就会等于n，n是数组越界后的第一个元素，如果它刚好是要查找的值呢？？

王老师，有一个疑惑不太明白 int mid = low + ((high - low)>>1) 这句，为什么要用这种写法呢？我看之前的简单的额二分查找是 int mid = (low + high)/2

今天的IP地址归属地问题，从工程实现的角度考虑，我更偏向于直接使用关系型数据库实现。 也就是将12w条归属地与IP区间的开始、结束存入数据库中。 数据库表ip_table有如下字段：area_name | start_ip | end_ip ，start_ip及end_ip 均建立索引 SQL语句： select area_name from ip_table where input_ip >= start_ip and input_ip <= end_ip; 学习算法的课程常常和自己工程开发的实际结合在一起，感觉两者是相互促进理解的过程。

老师，你说二分查找更适合用在“近似”查找问题，在这类问题上，二分查找的优势更加明显。这种问题链式哈希表不是更擅长吗？

老师你好，二分法查找在什么情况下low==high

通过ip找归属地时，是二分查找最后一个ip小于等于给定值的ip，这只是开始区间，请问老师那结束区间如何找呢？

为什么mid == n - 1，不是mid==high来判断更好吗？

Donald E.Knuth 叫 高德纳。高德纳”这个中文名字是1977年他访问中国之前所取的，命名者是储枫（姚期智的夫人，计算机科学家）。他的妻子叫高精兰（Jill）。 这个名字不应该音译的。

二分查找的变体问题，在java sdk、net framework中有实现吗？