On Saturday, 17 May 2014 at 20:30:30 UTC, bearophile wrote:
Sorry, I didn't know the linked list is sorted. It's scanned
sequentially, because you can't use a binary search on a
regular linked list. Perhaps a skiplist is better to avoid
O(n^2) behavour in presence of attacks or degenerate cases (in
past the AA used a tree there).
Bye,
bearophile
*Technically*, for a sorted linked list (or forward iterators in
general), you can find the result with O(N) *walk* iterations,
but still only O(log(N)) *comparison* iterations.
So saying "you can't use binary search on a regular linked list"
is not quite 100% accurate. You can still get some bang for your
buck out of a degenerated algorithm.
http://www.cplusplus.com/reference/algorithm/binary_search/
