15 | 二分查找（上）：如何用最省内存的方式实现快速查找功能？

精选留言(130)

• 

  Jerry银银 置顶

  说说第二题吧，感觉争议比较大:
  假设链表长度为n，二分查找每次都要找到中间点(计算中忽略奇偶数差异):
  第一次查找中间点，需要移动指针n/2次；
  第二次，需要移动指针n/4次；
  第三次需要移动指针n/8次；
  ......
  以此类推，一直到1次为值
  
  总共指针移动次数(查找次数) = n/2 + n/4 + n/8 + ...+ 1，这显然是个等比数列，根据等比数列求和公式：Sum = n - 1.
  
  最后算法时间复杂度是：O(n-1)，忽略常数，记为O(n)，时间复杂度和顺序查找时间复杂度相同
  
  但是稍微思考下，在二分查找的时候，由于要进行多余的运算，严格来说，会比顺序查找时间慢
  
  
  -----------------
  以上分析，不知道是否准确，还请老师解答

  作者回复: 分析的很好 👍 同学们可以把这条顶上去了

  2018-10-25

   6

   498
• 

  蒋礼锐 置顶

  因为要精确到后六位，可以先用二分查找出整数位，然后再二分查找小数第一位，第二位，到第六位。
  
  整数查找很简单，判断当前数小于+1后大于即可找到，
  
  小数查找举查找小数后第一位来说，从x.0到(x+1).0，查找终止条件与整数一样，当前数小于，加0.1大于，
  
  后面的位数以此类推，可以用x*10^(-i)通项来循环或者递归，终止条件是i>6，
  
  想了一下复杂度，每次二分是logn，包括整数位会查找7次，所以时间复杂度为7logn。空间复杂度没有开辟新的储存空间，空间复杂度为1。
  
  没有具体用代码实现，只是思路，还请多多指正。之后会用js去实际实现。

  2018-10-24

   1

   45
• 

  Jerry银银

  个人觉得二分查找进行优化时，还个细节注意：
  将mid = lo + (hi - lo) /2，将除法优化成移位运算时，得注意运算符的优先级，千万不能写成这样：mid = lo + (hi - lo) >> 1

  作者回复: 👍

  2018-10-26

   6

   136
• 

  朱凯

  二分法求一个数x的平方根y？
  解答：根据x的值，判断求解值y的取值范围。假设求解值范围min < y < max。若0<x<1，则min=x，max=1；若x=1，则y=1；x>1，则min=1，max=x；在确定了求解范围之后，利用二分法在求解值的范围中取一个中间值middle=(min+max)÷2，判断middle是否是x的平方根？若(middle+0.000001)*(middle+0.000001)＞x且(middle-0.000001)*(middle-0.000001)<x，根据介值定理，可知middle既是求解值;若middle*middle > x，表示middle＞实际求解值，max=middle; 若middle*middle ＜ x，表示middle＜实际求解值，min =middle;之后递归求解！
  备注：因为是保留6位小数，所以middle上下浮动0.000001用于介值定理的判断

  2018-10-25

   1

   87
• 

  Alexis何春光

  现在在cmu读研，正在上terry lee的data structure，惊喜的发现不少他讲的点你都涵盖了，个别他没讲到的你也涵盖了.... （当然可能因为那门课只有6学时，时间不足，但还是给这个专栏赞一个！）

  作者回复: 读cmu 太厉害了 仰慕

  2018-11-12

   7

   75
• 

  Dwyane

  1、low=mid+1，high=mid-1 学习了比较严谨条件
  
  
  2、二分法求根号5
  
  a:折半：       5/2=2.5
  
  b:平方校验:  2.5*2.5=6.25>5，并且得到当前上限2.5
  
  c:再次向下折半:2.5/2=1.25
  
  d:平方校验：1.25*1.25=1.5625<5,得到当前下限1.25
  
  e:再次折半:2.5-(2.5-1.25)/2=1.875
  
  f:平方校验：1.875*1.875=3.515625<5,得到当前下限1.875
  
  每次得到当前值和5进行比较，并且记下下下限和上限，依次迭代，逐渐逼近平方根：
  

  2018-12-21

   1

   42
• 

  锐雨

  求平方根，可以参考0到99之间猜数字的思路，99换成x, 循环到误差允许内即可，注意1这个分界线。欢迎交流，Java如下
  public static double sqrt(double x, double precision) {
  if (x < 0) {
  return Double.NaN;
  }
  double low = 0;
  double up = x;
  if (x < 1 && x > 0) {
  /** 小于1的时候*/
  low = x;
  up = 1;
  }
  double mid = low + (up - low)/2;
  while(up - low > precision) {
  if (mid * mid > x ) {//TODO mid可能会溢出
  up = mid;
  } else if (mid * mid < x) {
  low = mid;
  } else {
  return mid;
  }
  mid = low + (up - low)/2;
  }
  return mid;
  }

  2018-10-24

   1

   27
• 

  三忌

  def sqrt(x):
      '''
      求平方根，精确到小数点后6位
      '''
      low = 0
      mid = x / 2
      high = x
      while abs(mid ** 2 - x) > 0.000001:
          if mid ** 2 < x:
              low = mid
          else:
              high = mid
          mid = (low + high) / 2
      return mid

  2018-10-24

   5

   25
• 

  姜威

  总结：二分查找（上）
  一、什么是二分查找？
  二分查找针对的是一个有序的数据集合，每次通过跟区间中间的元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间缩小为0。
  二、时间复杂度分析？
  1.时间复杂度
  假设数据大小是n，每次查找后数据都会缩小为原来的一半，最坏的情况下，直到查找区间被缩小为空，才停止。所以，每次查找的数据大小是：n，n/2，n/4，…，n/(2^k)，…，这是一个等比数列。当n/(2^k)=1时，k的值就是总共缩小的次数，也是查找的总次数。而每次缩小操作只涉及两个数据的大小比较，所以，经过k次区间缩小操作，时间复杂度就是O(k)。通过n/(2^k)=1，可求得k=log2n，所以时间复杂度是O(logn)。
  2.认识O(logn)
  ①这是一种极其高效的时间复杂度，有时甚至比O(1)的算法还要高效。为什么？
  ②因为logn是一个非常“恐怖“的数量级，即便n非常大，对应的logn也很小。比如n等于2的32次方，也就是42亿，而logn才32。
  ③由此可见，O(logn)有时就是比O(1000)，O(10000)快很多。
  三、如何实现二分查找？
  1.循环实现
  代码实现：
  public int binarySearch1(int[] a, int val){
  int start = 0;
  int end = a.length - 1;
  while(start <= end){
  int mid = start + (end - start) / 2;
  if(a[mid] > val) end = mid - 1;
  else if(a[mid] < val) start = mid + 1;
  else return mid;
  }
  return -1;
  }
  注意事项：
  ①循环退出条件是：start<=end，而不是start<end。
  ②mid的取值，使用mid=start + (end - start) / 2，而不用mid=(start + end)/2，因为如果start和end比较大的话，求和可能会发生int类型的值超出最大范围。为了把性能优化到极致，可以将除以2转换成位运算，即start + ((end - start) >> 1)，因为相比除法运算来说，计算机处理位运算要快得多。
  ③start和end的更新：start = mid - 1，end = mid + 1，若直接写成start = mid，end=mid，就可能会发生死循环。
  2.递归实现
  public int binarySearch(int[] a, int val){
  return bSear(a, val, 0, a.length-1);
  }
  private int bSear(int[] a, int val, int start, int end) {
  if(start > end) return -1;
  int mid = start + (end - start) / 2;
  if(a[mid] == val) return mid;
  else if(a[mid] > val) end = mid - 1;
  else start = mid + 1;
  return bSear(a, val, start, end);
  }
  四、使用条件（应用场景的局限性）
  1.二分查找依赖的是顺序表结构，即数组。
  2.二分查找针对的是有序数据，因此只能用在插入、删除操作不频繁，一次排序多次查找的场景中。
  3.数据量太小不适合二分查找，与直接遍历相比效率提升不明显。但有一个例外，就是数据之间的比较操作非常费时，比如数组中存储的都是长度超过300的字符串，那这是还是尽量减少比较操作使用二分查找吧。
  4.数据量太大也不是适合用二分查找，因为数组需要连续的空间，若数据量太大，往往找不到存储如此大规模数据的连续内存空间。
  五、思考
  1.如何在1000万个整数中快速查找某个整数？
  ①1000万个整数占用存储空间为40MB，占用空间不大，所以可以全部加载到内存中进行处理；
  ②用一个1000万个元素的数组存储，然后使用快排进行升序排序，时间复杂度为O(nlogn)
  ③在有序数组中使用二分查找算法进行查找，时间复杂度为O(logn)
  2.如何编程实现“求一个数的平方根”？要求精确到小数点后6位？

  2018-10-31

   1

   20
• 

  Smallfly

  1. 求平方根可以用二分查找或牛顿迭代法;
  2. 有序链表的二分查找时间复杂度为 O(n)。

  2018-10-24

  

   16
• 

  THROW

  1000w数据查找这个，在排序的时候不就可以找到了么？

  作者回复: 如果是多次查找操作呢

  2018-10-24

   1

   16
• 

  Victor

  开篇的问题：1000w 个 8字节整数的中查找某个整数是否存在，且内存占用不超过100M ？ 我尝试延伸了一些解决方案：
  1、由于内存限制，存储一个整数需要8字节，也就是 64 bit。此时是否可以考虑bitmap这样的数据结构，也就是每个整数就是一个索引下标，对于每一个索引bit，1 表示存在，0 表示不存在。同时考虑到整数的数据范围，8字节整数的范围太大，这是需要考虑压缩的问题，压缩方案可以参考 RoaringBitmap 的压缩方式。
  2、我们要解决的问题，也就是判断某个元素是否属于某个集合的问题。这里是否可以和出题方探讨是否严格要求100%判断正确。在允许很小误差概率的情景下（比如判断是否在垃圾邮件地址黑名单中），可以考虑 BloomFilter 。
  BloomFilter 存储空间更加高效。1000w数据、0.1%的误差下需要的内存仅为 17.14M
  时间复杂度上，上面两种都是 hashmap的变种，因此为 o(1)。

  2018-10-27

  

   9
• 

  kaka

  关于求平方根的题，我知道一种比较巧妙的方法，那就是利用魔数，时间复杂度是 O(1)，根据我测试，精度大概能精确到 5 位小数，也还不错。下面是 c 语言代码
  
  float q_rsqrt(float number) {
      int i;
      float x2, y;
      const float threehalfs = 1.5;
      x2 = number * 0.5;
      y = number;
      i = *(int*)&y;
      i = 0x5f3759df - (i >> 1);
      y = *(float*)&i;
      y = y * (threehalfs - (x2 * y * y));
      y = y * (threehalfs - (x2 * y * y));
      y = y * (threehalfs - (x2 * y * y));
  
      return 1.0 / y;
  }

  2018-10-29

  

   8
• 

  啊波次的额佛哥～

  平方根C代码，precision位数，小数点后6位是0.000001
  double squareRoot(double a , double precision){
      double low,high,mid,tmp;
      if (a>1){
          low = 1;
          high = a;
      }else{
          low = 1;
          high = a;
      }
      while (low<=high) {
          mid = (low+high)/2.000;
          tmp = mid*mid;
          if (tmp-a <= precision && tmp-a >= precision*-1){
              return mid;
          }else if (tmp>a){
              high = mid;
          }else{
              low = mid;
          }
      }
      return -1.000;
  }
  int main(int argc, const char * argv[]) {
      double num = squareRoot(2, 0.000001);
      printf("%f",num);
      return 0;
  }

  2018-10-29

   2

   5
• 

  Liam

  链表的二分查找，每次查找的时间复杂度都为当前数据规模的一半，所以最坏情况下：
  查找次数f(n) = n + n/2 + n/4 + n/8 + ... + 1 = n(1 + 1/2 + 1/4 + ... 1/n)
  
  情况1： n = 2^k, 根据等比数列公式 f(n) = 2^k * ( 1 - (1/2) ^k) / (1 - 1/2) = 2n - 1
  情况2：n != 2^k, 假设k无穷大，则limf(n) = n ( 1 / (1 - 1/2)) = 2n, 实际上k < +∞， 所以
  f(n) < lim f(n) = 2n => f(n) = 2n-1
  
  综上所述，f(n) = 2n - 1, 时间复杂度为O(n)
  

  2018-10-26

  

   4
• 

  追风者

  王老师，考研的话可以以这个课程作为数据结构第一轮的基础复习吗。如果可以，还需要补充其他概念知识吗

  作者回复: 概念知识应该全了 考研的话还要看看考纲吧

  2018-10-24

  

   4
• 

  王小李

  平方根可以用牛顿迭代实现。

  作者回复: 哈哈 同学的回答超纲了 👍

  2018-10-24

  

   4
• 

  刘伟、

  关于1000万数中快速查找某个整数，我有个想法。考虑用数组下标来存储数据，一个bit位来存储标记。第一次排序的时候能得到这组数的最大值和最小值。 假如最小是5，最大是2000万。那我们定义一个字节数组Byte arr[2000万]，因为我只需要打标记，所以一个bit能存下标记，一个byte能存8个数。只需要2MB多一点就能存2000万个数的状态（存在还是不存在）
  先把这1000万个数存进去，用数x/8得到下标。用数x%8得到余数，因为每8个数一组得到的数组下标相同，所以还需要通过余数来确定具体是哪一个数。之后开始设置状态，从低位到高位，每一位代表一个数的状态，case0到7，每一次设置当下号码的状态时，先用按位于计算把其他不相关位置为1，当前位置为0，然后按位或对当前位置设置状态。存在就设置位1 ，不存在就设置位0
  上述操作执行完之后，就支持任意查找了。只需要输入一个数x，我就能立刻通过x/8和x%8得到当前这个数的位置，然后把这个位置的状态位数字取出来。如果是1表示存在，如果是0表示不存在。
  不知道这个想法有没有什么漏洞。希望老师或者一起学习的同学能帮忙一起想想

  作者回复: 赞 不错！

  2019-06-02

  

   3
• 

  yu🐟

  /**
       * 求一个数的平方根
       *
       * @param n：待求的数
       * @param deltaThreshold 误差的阈值
       * @return
       */
      public static double getSqureRoot(int n, double deltaThreshold) {
          double low = 1.0;
          double high = (double) n;
          while (low <= high) {
              double mid = low + ((high - low) / 2);
              double square = mid * mid;
              double delta = Math.abs(square / n - 1);
              if (delta < deltaThreshold) {
                  return mid;
              } else if (square < n) {
                  low = mid;
              } else {
                  high = mid;
              }
          }
          return -1.0;
      }

  2019-01-03

   2

   3
• 

  Kudo

  二分查找Python实现：
  1、非递归方式
  def bsearch(ls, value):
      low, high = 0, len(ls)-1
      while low <= high:
          mid = low + (high - low) // 2
          if ls[mid] == value:
              return mid
          elif ls[mid] < value:
              low = mid + 1
          else:
              high = mid - 1
      return -1
  
  2、递归方式
  def bsearch(ls, value):
      return bsearch_recursively(ls, 0, len(ls)-1, value)
      
  def bsearch_recursively(ls, low, high, value):
      if low > high:
          return -1
      mid = low + (high - low) // 2
      if ls[mid] == value:
          return mid
      elif ls[mid] < value:
          return bsearch_recursively(ls, mid+1, high, value)
      else:
          return bsearch_recursively(ls, low, mid-1, value)

  2018-10-25

  

   3