在單個鏈接列表上進行二進制搜索

Question

如何在單個鏈接列表上執行二進制搜索？如果有任何特定的方法，它也可以做到。 EP無法預先知道該列表中有多少元素，我必須在q> prox和p之間搜索並輸入一個單元格。

Answer 1

通常情況下這是不可能的，因爲二分查找需要隨機訪問，而單鏈表只能提供前向順序訪問。無法在內存中跳轉並查看某個nth元素（通過直接隨機訪問或跳過列表），我們最終需要從頭到尾線性搜索列表，即使它是排序的。