算法笔记（九）：二分查找

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法笔记（九）：二分查找，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1480字，纯文字阅读大概需要3分钟。

内容图文

（一）二分查找

1、例如：抱着一堆书走出图书馆的时候，检测器突然响了（其中一本书没有消磁），现在要检查哪一本书没有消磁。

（1）比较耗时的方式就是，一本一本书用检测器都检查下。

（2）比较快的方式是：分成相等的2份，分别给检测器检测。引起报警的那一份，再分成2份，分别给检测器检测，重复这个过程，直到找到引起报警的那本书。

    第二种方式就体现了二分查找思想。

2、二分查找依赖的是顺序表结构，简单的说就是数组。（二分查找需要按照下标随机访问元素，用其他数据结构，例如链表的话，时间复杂度会变高）

3、二分查找针对的是有序数据。

4、数据量太小不适合二分查找（因为此时遍历、二分查找花的时间差不多）

5、数据量太大也不适合二分查找。（二分查找底层依赖数组这种数据结构，而数组需要连续的内存空间，如果数据量太大，太耗内存。）

6、二分查找的时间复杂度为O（logn）

（二）练习题

1、实现“求一个数的平方根”，精确到小数点后 6 位。

 1 def mySqrt(n):
 2     l = 0
 3     r = n + 1
 4     while l < r:
 5         mid = l + (r - l) // 2
 6         if mid ** 2 == n:
 7             return "{}.000000".format(mid)
 8         elif mid ** 2 < n:
 9             l = mid + 1
10         elif mid ** 2 > n:
11             r = mid
12     inte = l -1   # 开方整数部分
13     result = inte + 0.5  # 该行及下面的for循环根据开方公式计算小数部分
14     for i in range(1,7):
15         result = result + (n/result - result)*0.5
16         result = str(result).split(".")
17         result = float("{}.{}".format(result[0],result[1][:i]))  # 保留小数位，根据开方计算公式，一次保留1、2、3...位小数
18     return result
19 
20 print(mySqrt(5))

 

 

内容总结

以上是互联网集市为您收集整理的算法笔记（九）：二分查找全部内容，希望文章能够帮你解决算法笔记（九）：二分查找所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---