2 phoenix850121 phoenix850121 于 2017.09.14 14:23 提问

java集合二分查找算分

只有采用随机访问,二分查找才有意义,如果提供的是一个链表,binarySearch()就 自动的变成线性查找。没太理解这句话的意思。链表是有序集合,为什么二分查找用在链表上就变成线性查找?

多谢各位老师指教。

2个回答

Runner__1
Runner__1   Rxr 2017.09.14 14:30
已采纳

举个例子,比如一个长度为10的表结构(已经排序过的),首先和第5位的元素进行比较,若目标值小于第5位上的元素,那么认为目标在第1位到第5位这个区间内,接着比较目标值和第3位的元素,如果是数组,也就是这里说的随机访问的结构,可以直接通过下标来访问第3位的元素,而对于链表来说,它始终要从第一个元素一个一个地遍历过来才能找到第3位的元素,由于这样的过程就使得二分查找变成了顺序查找

phoenix850121
phoenix850121 我明白了,忽谢谢。略了java有一句介绍LinkedList的话,LinkedList<> list =...; String obj = list.get(n); 虽然有get方法,但效率低。
2 个月之前 回复
zhuoyue93
zhuoyue93   2017.09.14 14:36

因为链表没有下标,不能跳跃,只能一个一个查找

Csdn user default icon
上传中...
上传图片
插入图片