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

精选留言

• 
  Smallfly

  2018-10-27 10:49:06

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

  2018-10-31 16:50:52

  思考题对应leetcode 33题，大家可以去练习
• 
  舍得

  2018-10-27 18:04:57

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

  作者回复

  谢谢指正 我稍后改下

  2018-10-29 19:24:13

• 
  谁呢

  2019-03-05 09:43:18

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

  作者回复

  下面的写法有可能会导致溢出，比如low很大，high也很大，之和就溢出了。

  2019-03-05 10:26:36

• 
  毅仔

  2018-12-23 12:20:22

  第一次见到逻辑这么清晰的二分查找代码，已经被老师俘获了，太优雅了
• Geek_86533a

  2019-08-05 10:29:21

  茅塞顿开，刷leetcode的时候，看大神们写的二分查找，找一个数字出现的左右边界，始终无法理解，现在才明白自己陷入了追求代码简洁的误区。感谢老师渡我出苦海！
• 
  John

  2020-05-16 03:18:10

  我来给初学者解释一下IP地址的事吧. 为什么说IP地址可以转化为32位的整数呢? 首先我们看IP地址都是张这样的: "XXX.XXX.XXX.XXX" 一共4段,每段3位(因为你从来没有见过4位的一段的吧). 我们知道2的10次方是1024(程序员记得10月24号这个节日吧), 所有很容易掐指一算得到2^9=512 => 2^8=256. 其实xxx的上限是255, 这是IP地址的规定(反正你也没见过3xx或者4xx的地址吧)!!! 也就是说对于[0, 256)=[0, 255] 这个区间对应的2进制是8位. 刚才说了是4段, 那么就是4*8=32位的2进制喽. 当然了, 我们这段只是论证了对应的2进制是32位而已, 你对这道题的操作倒也不必一定要转化为2进制, 其实也可以干脆把小数点直接抽掉+补上前面的0, 得到一个很大的十进制数字. 这样的后果第一保持顺序的稳定性(其实也没有重复的), 第二很容易从十进制大数转回IP地址. 比如这样 "255.128.16.8 => 255128016008", 最后搜索结束之后再转回去 "255128016008=>255128016008"就可以啦!
• 
  Victor

  2018-10-27 22:38:14

  今天的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;
  学习算法的课程常常和自己工程开发的实际结合在一起，感觉两者是相互促进理解的过程。

  作者回复

  数据库可以 单性能会受限

  2018-10-28 23:27:38

• 
  charon

  2018-10-26 15:32:49

  用JavaScript实现的最基本的思考题：
  array是传入的数组，value是要查找的值
  思路是通过对比low,high的值来判断value所在的区间，不用多循环一遍找偏移量了~
  function search(array,value){
  let low = 0;
  let high = array.length - 1;
  
  while(low <= high){
  let mid = low + ((high - low) >> 1);
  if(value == array[low]) return low;
  if(value == array[high]) return high;
  if(value == array[mid]) return mid;
  
  if(value > array[mid] && value > array[high] && array[mid] < array[low]){
  high = mid - 1;
  }else if(value < array[mid] && value < array[low] && array[mid] < array[low]){
  high = mid - 1;
  }else if(value < array[mid] && value > array[low]){
  high = mid - 1;
  }else{
  low = mid + 1;
  }
  }
  
  return -1
  }
• 松鼠鱼

  2020-04-05 00:42:56

  尝试了一下LeetCode的33题，试提供一个Java版本的解法。从提交反馈来看还是不错的：
  Runtime: 0 ms, faster than 100.00% of Java online submissions for Search in Rotated Sorted Array.
  
  public int solution(int[] nums, int target) {
  int s = 0;
  int e = nums.length - 1;
  while (e >= s){
  int mid = s + (e-s)/2;
  if (nums[mid] == target) return mid;
  if (nums[mid] < nums[e]) {
  if (target < nums[mid] || target > nums[e]) {
  e = mid - 1;
  } else s = mid + 1;
  } else {
  if (target < nums[s] || target > nums[mid]) {
  s = mid + 1;
  } else e = mid - 1;
  }
  }
  return -1;
  }
• 
  姜威

  2018-11-03 10:05:11

  总结：二分查找（下）
  一、四种常见的二分查找变形问题
  1.查找第一个值等于给定值的元素
  2.查找最后一个值等于给定值的元素
  3.查找第一个大于等于给定值的元素
  4.查找最后一个小于等于给定值的元素
  二、适用性分析
  1.凡事能用二分查找解决的，绝大部分我们更倾向于用散列表或者二叉查找树，即便二分查找在内存上更节省，但是毕竟内存如此紧缺的情况并不多。
  2.求“值等于给定值”的二分查找确实不怎么用到，二分查找更适合用在”近似“查找问题上。比如上面讲几种变体。
  三、思考
  1.如何快速定位出一个IP地址的归属地？
  [202.102.133.0, 202.102.133.255] 山东东营市
  [202.102.135.0, 202.102.136.255] 山东烟台
  [202.102.156.34, 202.102.157.255] 山东青岛
  [202.102.48.0, 202.102.48.255] 江苏宿迁
  [202.102.49.15, 202.102.51.251] 江苏泰州
  [202.102.56.0, 202.102.56.255] 江苏连云港
  假设我们有 12 万条这样的 IP 区间与归属地的对应关系，如何快速定位出一个IP地址的归属地呢？
  2.如果有一个有序循环数组，比如4，5，6，1，2，3。针对这种情况，如何实现一个求“值等于给定值”的二分查找算法？
• 
  朱坤

  2019-02-25 00:24:16

  置顶的同学的思路一，即先找分界再判断在哪个数组，再二分，其实是可以做到O(Log N)的，找分界的点的规则就是找到首个小于a[0]的元素，思路用老师4个转换问题的解法就可以。按评论做了下leetcode33题，感觉会比较老师给的思考题描述清晰。。因为老师说的找问题，没有明确有几组循环数组。。
• 疾风狂草

  2018-12-10 00:20:22

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

  作者回复

  哈希表是精准查找

  2018-12-10 09:54:57

• 
  菜鸡程序员

  2018-12-07 10:25:08

  
  1.如果不知道分界点，找寻分界点没有意义，不如直接遍历。
  2.如果知道分界点，查看在哪一边，然后二分法，或者偏移量计算,二分法
  
  老师,我今天这种可以吗:
  /**
  * 功能描述:查找第一个大于等于给定值的元素
  *
  * @param null
  * @return
  * @author xiongfan
  * @date 2018/12/7 9:43:00
  */
  public static int getFirstGreaterValue(int[] array,int value) {
  int low = 0;
  int high = array.length - 1;
  
  while (low <= high) {
  int mid = low + (high - low) >> 1;
  if (array[mid] < value) {
  low = mid + 1;
  } else if (array[mid] > value) {
  high = mid - 1;
  } else {
  
  if (mid == 0 || array[mid - 1] < array[mid]) {
  return mid;
  }
  high = mid - 1;
  
  }
  }
  
  return low>array.length-1?-1:low;
  }
  
  /**
  * 功能描述:查找最后一个小于等于给定值的元素
  *
  * @param null
  * @return
  * @author xiongfan
  * @date 2018/12/7 10:03:00
  */
  public static int getLastLessValue(int[] array,int value) {
  int low = 0;
  int high = array.length - 1;
  
  while (low <= high) {
  int mid = low + (high - low) >> 1;
  if (array[mid] > value) {
  high = mid - 1;
  } else if (array[mid] < value) {
  low = mid + 1;
  } else {
  if (mid > array.length-1 || array[mid] < array[mid + 1]) {
  return mid;
  }
  low = mid + 1;
  }
  }
  
  return high<0?-1:high;
  }
  
• 
  勤劳的小胖子-libo

  2018-10-27 10:30:56

  1. 先二分遍历找到分隔点index，特征是<pre, >=next;
  2. 把数组分成二个部分，[0,index-1], [index,length-1];
  3. 分别使用二分查找，找到给定的值。
  时间复杂度为2*log(n). 不确定有什么更好的办法。
  
• 
  牛顿的苹果啦

  2019-01-31 17:41:19

  思考题：
  可以考虑将数组分为N个有序数组，分别进行二分查找。
  代码实现：
  public int circleBinarySearch(int[] a, int value){
  int low = 0, high=0;
  for(int i=0;i<a.length-1;i++){
  //找到有序数组的下标
  if(a[i]<a[i+1]){
  high=i+1;
  }else{
  //有序数组到顶，二分查找
  int i1 = binarySearch(low, high, a, value);
  if(-1 != i1){
  return i1;
  }else{
  low = high+1;
  }
  }
  //high已经到最后一个位置
  if(a.length-1 == high){
  return binarySearch(low, high, a, value);
  }
  }
  return -1;
  }
  
  private int binarySearch(int low, int high, int[] a, int value){
  for(;low<=high;){
  int middle = low+((high-low)>>1);
  if(a[middle] == value){
  return middle;
  }
  if(a[middle] > value){
  high = middle -1;
  }else{
  low = middle +1;
  }
  }
  return -1;
  }
• 
  狼的诱惑

  2018-10-31 13:15:22

  @老师，请老师或其他高人回复指教
  /**
  * 例如： 4 5 6 1 2 3
  * 循环数组的二分查找 总体时间复杂度O(n)
  */
  public static int forEqualsThan(int[] arr, int num) {
  if (arr[0] == num) {
  return 0;
  }
  int length = arr.length;
  int low = 0;
  int high = length - 1;
  //找到循环节点
  for (int i = 0; i < length; i++) {
  if (i == length - 1) {
  if (arr[i] > arr[0]) {
  low = i;
  high = 0;
  break;
  }
  } else {
  if (arr[i] > arr[i + 1]) {
  low = i;
  high = low + 1;
  break;
  }
  }
  }
  //判断第一个节点的大小位置，确定low和high的值，转变为正常有序的二分查找
  if (arr[0] < num) {
  high = low;
  low = 0;
  }
  if (arr[0] > num) {
  low = high;
  high = length - 1;
  }
  while (low <= high) {
  int index = low + ((high - low) >> 1);
  if (arr[index] > num) {
  high = index - 1;
  }
  if (arr[index] < num) {
  low = index + 1;
  }
  if (arr[index] == num) {
  return index;
  }
  }
  return -1;
  }
• 
  低调人生

  2019-05-28 17:05:18

  我觉得查找第一个符合给定的值得那两种写法 第一种更好理解 没看懂作者的写法
• 
  晓杉

  2018-11-16 10:20:29

  老师，我有一个疑问。
  使用二分查找的前提是有序数组。
  对于本节IP地址问题，我们先进行排序再进行查找，我理解应该时间复杂度是排序平均O(nLogn)再加上二分查找O(logn)
  比单纯的顺序遍历O(n)要慢许多了。
  是不是实际中，这种无序情况直接使用了顺序遍历查找呢？
• 
  刘忽悠

  2018-10-26 01:45:18

  第一段代码的想法确实妙，乍眼一看还以为这段代码有问题