在链表数据结构上可以进行二分查找,但完全没有必要使用它,因为它会花费与普通线性搜索相同的时间。
为了实现二分查找,我们需要两个先决条件:
- 数据必须有序排列。
- 可以在恒定时间内访问任何随机元素。
对于链表,第二个先决条件不满足,因为链表中的元素并不是一个接一个连续存储在同一块内存空间,而是存储在随机位置,链表中任何一个元素都必须从头节点开始遍历。
而对于数组来说,任何元素都可以在恒定的时间内访问,因为:
元素的地址 = 数组的基址 + 元素的索引 * 元素占用的内存空间
反过来,这也回答了为什么数组的每个元素都要使用相同的数据类型。数据类型相同,每个元素占用的内存空间也就相同,那么通过索引就能计算得出元素的地址。