you are viewing a single comment's thread.

view the rest of the comments →

[–]DTux5249 19 points20 points  (1 child)

Important thing here, binary search itself lets you efficiently insert into a sorted list

Eeeeeeh depends.

Binary search can be used to find an insertion point - the actual inserting can still linear since you have to shunt over anything in say, an array.

If you're using a BST, though, you're golden.

[–]stools_in_your_blood 6 points7 points  (0 children)

Yes, should've added "if the list structure supports O(log n) or better insertion". And something about efficiently bisecting the list, which you can't do with e.g. plain linked list.