精选留言(242)

• 
  Jerry银银

  置顶

  2018-10-25

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

  展开

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

  共 33 条评论

  1116
• 
  蒋礼锐

  置顶

  2018-10-24

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

  展开

  共 15 条评论

  117
• 
  Jerry银银

  2018-10-26

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

  作者回复: 👍

  共 15 条评论

  305
• 
  Alexis何春光

  2018-11-12

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

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

  共 24 条评论

  211
• 
  朱凯

  2018-10-25

  二分法求一个数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用于介值定理的判断

  展开

  共 6 条评论

  162
• 
  Dwyane

  2018-12-21

  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进行比较，并且记下下下限和上限，依次迭代，逐渐逼近平方根：

  展开

  共 4 条评论

  150
• 
  三忌

  2018-10-24

  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

  展开

  共 10 条评论

  59
• 
  刘伟、

  2019-06-02

  关于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表示不存在。 不知道这个想法有没有什么漏洞。希望老师或者一起学习的同学能帮忙一起想想

  展开

  作者回复: 赞 不错！

  共 12 条评论

  40
• 
  锐雨

  2018-10-24

  求平方根，可以参考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; }

  展开

  共 5 条评论

  40
• 
  姜威

  2018-10-31

  总结：二分查找（上） 一、什么是二分查找？ 二分查找针对的是一个有序的数据集合，每次通过跟区间中间的元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间缩小为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位？

  展开

  共 9 条评论

  36
• 
  THROW

  2018-10-24

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

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

  共 6 条评论

  32
• 
  Smallfly

  2018-10-24

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

  

  26
• 
  Garwen

  2018-11-21

  第一题虽说是在二分查找的这一章，还是推荐大家用牛顿弦切法求解平方根，代码如下供大家参考： double number = 15; //待求平方根的数 double xini = 10;//初始点 while(xini*xini - number > 1e-6) { xini = (number + xini*xini)/2/xini; }

  展开

  作者回复: 👍

  共 4 条评论

  22
• 
  王小李

  2018-10-24

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

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

  共 2 条评论

  19
• 
  Jerry银银

  2019-03-30

  看了留言，求平方根那题，同学的答案可能都不对。因为题目没有要求必须返回正整数，所以将有两个答案：正的和负的！所以，算法的输出应该是一个数组。😝

  共 2 条评论

  14
• 
  Victor

  2018-10-27

  开篇的问题：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)。

  展开

  

  13
• 
  kaka

  2018-10-29

  关于求平方根的题，我知道一种比较巧妙的方法，那就是利用魔数，时间复杂度是 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; }

  展开

  共 1 条评论

  12
• 
  慧

  2019-12-16

  1.求一个数的平方根 问题咋一看与二分查找并无联系 细想思路正是利用二分查找的思路求解 public static Double squareRoot(int a){ double x = 0; double low = 0; double high = a; while(low<=high){ x = (low+high)/2; if(x*x>a){ high = x-0.000001; } if(x*x<a){ low = x+0.000001; } } return new BigDecimal(x).setScale(6, BigDecimal.ROUND_HALF_UP).doubleValue(); }

  展开

  共 1 条评论

  12
• 
  yu🐟

  2019-01-03

  /** * 求一个数的平方根 * * @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; }

  展开

  共 2 条评论

  6
• 
  啊波次的额佛哥～

  2018-10-29

  平方根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; }

  展开

  共 2 条评论

  6