Question

对第一题有疑问 1. 请问有序链表可以用二分查找吗？它符合二分查找的要求吗？ 2. 对分查找是不是

对第一题有疑问
1. 请问有序链表可以用二分查找吗？它符合二分查找的要求吗？
2. 对分查找是不是就是二分查找？
3. 如果是二分查找，最坏的情况不是也要log²n吗？

Answer 1

1、链表是不知道地址的，不能随机访问数据，所以用二分查找是不合适的。
2、这里对分查找应该就是二分查找吧
3、有序链表肯定是按照顺序查找比较方便，最坏情况是每个数都比较一次才找到，比较次数是n,
如果是二分查找，首先肯定得找到链接得中间位置，这里的长度为n，先循环n/2次得到中间位置，比较所查找值与中间位置的值大小，（二分查找最差情况是边缘值得时候，这里我们假设要查找的是最大值，看看比较次数），最大值肯定比中间值大，继续对中间位置的右边二分，右边的中间值查找所需循环次数为n/4, 依次类推是n/8、n/16
总的查找次数是n/2+n/4+n/8+n/16 +........≈ n
在脑海中想象一下最大值的二分查找，每个数其实都查找了一遍。

另外，这里说的比较次数，如果查找次数不算是比较次数的话，那比较次数应该是你说的log2n.
感觉这题的意思是将查找次数也算是比较次数了。
本题具体怎么解释应该要看出题人的意思了。