是否在 Elixir 中对有序列表 O(logN) 进行二进制搜索？
Is binary search for an ordered list O(logN) in Elixir?
对于有序列表，二分查找时间复杂度为O(logN)。但是在 Elixir 中，列表是链表，所以为了得到列表的中间元素，你必须迭代 N/2 次，这使得整体搜索复杂度为 O(NLogN)。
所以我的问题是：
- Is above time complexity correct?
- If it's correct, the binary search wouldn't make sense in Elixir, right? You have to iterate the list to get what you want, so the best is O(N).
是的，由于您所说的原因，几乎没有理由对链表进行二进制搜索。您需要一个随机访问数据结构（通常是数组）才能使二进制搜索有用。
可能会出现一个有趣的极端情况，其中元素的比较成本非常高，因为例如它们只是远程存储项目的句柄。在那种情况下，通过链表进行二分搜索可能仍然优于线性搜索，因为虽然需要更多操作 (O(N * log(N)))，但它需要较少的比较 (O(log(N)))，而线性搜索需要 O(N) 比较。
对于有序列表，二分查找时间复杂度为O(logN)。但是在 Elixir 中，列表是链表，所以为了得到列表的中间元素，你必须迭代 N/2 次，这使得整体搜索复杂度为 O(NLogN)。
所以我的问题是：
- Is above time complexity correct?
- If it's correct, the binary search wouldn't make sense in Elixir, right? You have to iterate the list to get what you want, so the best is O(N).
是的，由于您所说的原因，几乎没有理由对链表进行二进制搜索。您需要一个随机访问数据结构（通常是数组）才能使二进制搜索有用。
可能会出现一个有趣的极端情况，其中元素的比较成本非常高，因为例如它们只是远程存储项目的句柄。在那种情况下，通过链表进行二分搜索可能仍然优于线性搜索，因为虽然需要更多操作 (O(N * log(N)))，但它需要较少的比较 (O(log(N)))，而线性搜索需要 O(N) 比较。