只有采用随机访问,二分查找才有意义,如果提供的是一个链表,binarySearch()就 自动的变成线性查找。没太理解这句话的意思。链表是有序集合,为什么二分查找用在链表上就变成线性查找?
多谢各位老师指教。
只有采用随机访问,二分查找才有意义,如果提供的是一个链表,binarySearch()就 自动的变成线性查找。没太理解这句话的意思。链表是有序集合,为什么二分查找用在链表上就变成线性查找?
多谢各位老师指教。
举个例子,比如一个长度为10的表结构(已经排序过的),首先和第5位的元素进行比较,若目标值小于第5位上的元素,那么认为目标在第1位到第5位这个区间内,接着比较目标值和第3位的元素,如果是数组,也就是这里说的随机访问的结构,可以直接通过下标来访问第3位的元素,而对于链表来说,它始终要从第一个元素一个一个地遍历过来才能找到第3位的元素,由于这样的过程就使得二分查找变成了顺序查找