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

精选留言(159)

• 

  Smallfly 置顶

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

  2018-10-27

   9

   254
• 

  zixuan

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

  2018-10-31

   1

   88
• 

  舍得

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

  作者回复: 谢谢指正 我稍后改下

  2018-10-27

   2

   25
• 

  王艳红

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

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

  2019-03-05

   3

   22
• 

  Victor

  今天的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-27

   1

   15
• 

  charon

  用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
      }

  2018-10-26

  

   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。针对这种情况，如何实现一个求“值等于给定值”的二分查找算法？

  2018-11-03

   2

   7
• 

  朱坤

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

  2019-02-25

  

   6
• 

  菜鸡程序员

  
  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;
  }
  

  2018-12-07

  

   6
• 

  狼的诱惑

  @老师，请老师或其他高人回复指教
  /**
       * 例如： 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;
      }

  2018-10-31

   3

   5
• 

  牛顿的苹果啦

  思考题：
  可以考虑将数组分为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;
      }

  2019-01-31

  

   4
• 

  晓杉

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

  2018-11-16

   2

   4
• 

  勤劳的小胖子-libo

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

  2018-10-27

  

   4
• 

  komo0104

  给原来的index加上偏移量。
  比如原来的二分查找代码从0开始到n-1结束，现在为x到x - 1 (即n-1+x-n)。
  x为开始循环处的索引，例子里为3 （1所在索引）。需要扫描一遍数组找到x，复杂度O(n)。其余和普通二分查找一样，需要多判断index not out of bound。如果索引超过n了要减n。
  总的复杂度还是O(n)

  2018-10-26

  

   3
• 

  低调人生

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

  2019-05-28

   2

   2
• 

  毅仔

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

  2018-12-23

  

   2
• 

  QFann

  public int search(int[] nums, int target) {
          if(nums.length ==0) return -1;
          if(nums.length ==1){
              if(nums[0] == target) return 0;
              else return -1;
          }
          int low = 0;
          int high = nums.length - 1;
          int index = subIndex(nums,low,high);
          if(index != -1){
              int val = binarySearch(nums,low,index,target);
              if (val != -1) return val;
              return binarySearch(nums,index+1,high,target);
          }
          return binarySearch(nums,low,high,target);
      }
      
      public static int subIndex(int [] nums,int low,int high){
          while (low <= high){
              int mid = low + ((high - low )>> 1);
              if(nums.length < 1) return -1;
              if(nums[mid] > nums[mid+1]) return mid;
              else if( nums[mid] < nums[low] ) high = mid ;
              else if (nums[mid] > nums[high]) low = mid ;
              else return -1;
          }
          return -1;
      }
      
      public static int binarySearch(int[] nums,int low,int high,int target){
          while (low <= high){
              int mid = low + ((high - low)>>1);
              if(nums[mid] == target) return mid;
              else if (nums[mid] < target) low = mid + 1;
              else high = mid -1;
          }
          return -1;
      }

  2018-12-18

  

   2
• 

  Monday

  二分的四种变种写法。个人觉得都是分三种情况进行讨论，再多注意判断边界值，三种情况为：
  a[mid]<value
  a[mid]=value
  a[mid]>value；
  思考题：自己思考了一小段时间没有好的思路，就各学友的留言，亲自实现了Smallfly的方法三，感觉比较好！谢谢！

  2018-10-29

  

   2
• 

  Vilochen.

  文中的二分查找四道题实现：
  1.
  public static int searchFirst(int[] array, int num) {
          int l = 0;
          int h = array.length - 1;
          while (l < h) {
              int mid = (l + h) >>> 1;
              if (array[mid] < num) {
                  l = mid + 1;
              } else {
                  h = mid;
              }
          }
          if (array[l] == num) {
              return l;
          }
          return -1;
      }
  
   2. public static int searchFirstLarge(int[] array, int num) {
          int l = 0;
          int h = array.length - 1;
          while (l < h) {
              int mid = (l + h) >>> 1;
              if (array[mid] < num) {
                  l = mid + 1;
              } else {
                  h = mid;
              }
          }
          if (array[l] >= num) {
              return l;
          }
          return -1;
      }
  
    3. public static int searchLast(int[] array, int num) {
          int l = 0;
          int h = array.length - 1;
          while (l < h) {
              int mid = (l + h + 1) >>> 1;
              if (array[mid] > num) {
                  h = mid - 1;
              } else {
                  l = mid;
              }
          }
          if (array[l] == num) {
              return l;
          }
          return -1;
      }
  
   4. public static int searchLastSmall(int[] array, int num) {
          int l = 0;
          int h = array.length - 1;
          while (l < h) {
              int mid = (l + h + 1) >>> 1;
              if (array[mid] > num) {
                  h = mid - 1;
              } else {
                  l = mid;
              }
          }
          if (array[l] <= num) {
              return l;
          }
          return -1;
      }

  2019-11-18

  

   1
• 

  felix

  想到一种思路，依旧对半查找，但是现在两边会出现一个有序数组和循环数组，如果选择的数在有序数组内，正常的二分查找就OK，如果不是，继续对半，同上。次数和二分查找一致，所以依旧是logN，就是判断比较多点。

  2019-11-09

  

   1