在单个链接列表上进行二进制搜索

Question

如何在单个链接列表上执行二进制搜索？如果有任何特定的方法，它也可以做到。 EP无法预先知道该列表中有多少元素，我必须在q> prox和p之间搜索并输入一个单元格。

Answer 1

通常情况下这是不可能的，因为二分查找需要随机访问，而单链表只能提供前向顺序访问。无法在内存中跳转并查看某个nth元素（通过直接随机访问或跳过列表），我们最终需要从头到尾线性搜索列表，即使它是排序的。