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

精选留言(103)

• 
  Smallfly 置顶

  2018-10-27

   134

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

  展开
• 
  zixuan

  2018-10-31

   42

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

  展开
• 
  Victor

  2018-10-27

   9

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

  展开

  作者回复: 数据库可以 单性能会受限

• 
  王艳红

  2019-03-05

   8

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

  展开

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

• 
  charon

  2018-10-26

   8

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

   6

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

  展开

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

• 菜鸡程序员

  2018-12-07

   4

  
  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-11-03

   4

  总结：二分查找（下）
  一、四种常见的二分查找变形问题
  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-10-31

   4

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

   3

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

  展开
• 
  komo0104

  2018-10-26

   3

  给原来的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-12-23

   2

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

  2018-12-18

   2

  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-11-16

   2

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

  展开
• 
  Monday

  2018-10-29

   2

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

  展开
• 
  朱坤

  2019-02-25

   1

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

  展开
• 
  牛顿的苹果...

  2019-01-31

   1

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

   1

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

  展开

  作者回复: 哈希表是精准查找

• 
  Jeson

  2018-10-28

   1

  #查找第一个值等于给定值的元素
  def bsearchFirst(nums, val):
      low, high = 0, len(nums) - 1
      while low <= high:
          mid = low + ((high - low) >> 1)
          if nums[mid] >= val:
              high = mid - 1
          else:
              low = mid + 1
      if nums[low] == val:
          return low
      else:
          return None
  
  #查找最后一个值等于给定值的元素
  def bsearchLast(nums, val):
      low, high = 0, len(nums) - 1
      while low <= high:
          mid = low + ((high - low) >> 1)
          if nums[mid] <= val:
              low = mid + 1
          else:
              high = mid - 1
      if nums[high] == val:
          return high
      else:
          return None
  
  #查找第一个大于等于给定值的元素
  def bsearchFirstLargerEqual(nums, val):
      low, high = 0, len(nums) - 1
      while low <= high:
          mid = low + ((high - low) >> 1)
          if nums[mid] >= val:
              high = mid - 1
          else:
              low = mid + 1
      if nums[low] >= val:
          return low
      else:
          return None
  
  #查找最后一个小于等于给定值的元素
  def bSearchLastsmallerEqual(nums, val):
      low, high = 0, len(nums) - 1
      while low <= high:
          mid = low + ((high - low) >> 1)
          if nums[mid] <= val:
              low = mid + 1
          else:
              high = mid - 1
      if nums[high] <= val:
          return high
      else:
          return None
  
  #循环数组的二分查找
  def bSearchRecycle(nums, val):
      n, offset = len(nums), 3
      low, high = 0, n - 1
      while low <= high:
          mid = low + ((high - low) >> 1)
          midIdx = (mid + offset) % n
          if nums[midIdx] == val:
              return midIdx
          elif nums[midIdx] < val:
              low = mid + 1
          else:
              high = mid - 1
      return None
  
  if __name__ == '__main__':
      nums = [0, 0, 2, 2, 3, 3]
      val = 1
      print(bSearchLastsmallerEqual(nums, val))
  
      nums = [4, 5, 6, 1, 2, 3]
      val = 3
      print(bSearchRecycle(nums, val))

  展开
• 
  锐雨

  2018-10-27

   1

  关于循环有序数组的问题，假设array无重复元素的话，我们可以先二分法将array分成两个递增数组，再分别采用二分法。有不妥之处忘赐教哦, java：
  
      public static int search(int x, int[] array) {
          if (null == array || array.length == 0) {
              return -1;
          }
          /** Step1. 先找到循环队列新一轮从小变大的起始位置*/
          int low = 1;
          int high = array.length - 1;
          int mid;
          int firstVal = array[0];
          /*到firstVal之后第一个<firstVal的position */
          int dividePos = -1;
          while(low <= high) {
              mid = low + ((high - low)>>1);
              if (array[mid] > firstVal) {
                  low = mid + 1;
              } else {
                  if (mid == 1 || array[mid - 1] > firstVal) {
                      dividePos = mid;
                      break;
                  } else {
                      high = mid -1;
                  }
              }
          }
          /** Step2. 对dividePos两边分别进行二分搜索 */
          int targetPos = -1;
          if (dividePos >= 1) {
              targetPos = bSearch(x, array, 0, dividePos - 1);
              if (-1 != targetPos) {
                  return targetPos;
              } else {
                  targetPos = bSearch(x, array, dividePos, array.length - 1);
              };
          } else {
              targetPos = bSearch(x, array, 0, array.length - 1);
          }
          return targetPos;
      }
      
      /** 普通的二分搜索 */
      public static int bSearch(int x, int[] array, int low, int high) {
          if (null == array || array.length == 0 || low < 0 || high >= array.length) {
              return -1;
          }
          int mid;
          while(low <= high) {
              mid = low + ((high - low)>>1);
              if (array[mid] > x) {
                  high = mid - 1;
              } else if (array[mid] < x) {
                  low = mid + 1;
              } else {
                  return mid;
              }
          }
          return -1;
      }

  展开