我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:爱彩网 > 二分搜索 >

二分查找为什么不能用于链表

归档日期:07-04       文本归类:二分搜索      文章编辑:爱尚语录

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  这样你对于一次二分查找 [l,r) 区域,我可以通过简单的计算得到中间值 mid = (l+r)/2 对应的值

  而对于链表,每个节点对应的坐标是不确定的,比如查找 [0,4) ,我需要比较mid = (0+4)/2 = 2 的值

  然后电脑就开始找,从0开始往后找到1,找到1再往下找……经过千辛万苦才能找到 a[2] 位于0x0010 这个地址

  理论而言,我们每次都需要遍历整个查询区域二分之一长度的数据,也即 T(n/2)

  再加上二分查找本身的 T(logn) 总的时间复杂度是 O(nlogn) 甚至比你直接遍历链表查询更慢!

本文链接:http://pikeducation.com/erfensousuo/478.html