讨论/《二分查找》 - 它是如何工作的?/
《二分查找》 - 它是如何工作的?
共 15 个回复

二分查找条件是先有序

19

最开始知道二分查找是在MIT的CS课程上,老师当场撕书,每次撕一半然后做比较。

7

首先,排序再二分的复杂度是 nlog(n)+log(n)n \log(n) + \log(n) 而不是相乘。其次,(假设没错) nlog(n)log(n)=O(n2)n\log(n)*\log(n)=O(n^2) 这样的说法虽然没问题,但是不够严谨。比如说在一个数组中进行 kk 次查找,如果依次扫一遍的话复杂度为 O(nk)O(nk), 而排序预处理之后再依次进行二分查找复杂度是 O(nlogn+klogn)O(n\log n +k\log n), 在 kk 较大的时候(比如 k>=nk >= n 时)后者的时间复杂度优于前者。

1

理解不对

你说的太片面,二分查找核心是每次折半查询有条件区分一半数据

打卡打卡,做题时知道用二分,细节一直处理不好,过来学一遍

二分查找的前提:
1.数据必须是有序的
2.数据必须是有边界的
3.数据是可以通过索引获取的

小白打卡

你说的对,已改

打卡