Sort on a list can be done in O(n*log(n))
using merge sort
. However there is a bigger problem - binary search can not be applied on the list precisely because of the lack of random access.
Still please note that a list can be implemented in many different ways, including using an array as backing and in that case you will also have random access(this is not the case with std::list
, though).
The best solution to the problem is to use a std::vector
and perform binary search on it(after you sort it). This way you know there is random access operator.
EDIT: as it seems the values in your container can change interactively, pre-sorting and then performing a binary search is not an option. It is so because after you insert a new value, you will have to sort the elements again. More complex version of list like skip list support that, but otherwise set should be faster by far.