I wish to search for an integer in a vector of integer. I have two candidates for the job:
It seems that Binary Search is the best candidate for the job as although I have to sort the vector, the total running time will be O(NLog2N)
assuming quicksort take O(NLog2N)
and searching takes O(Log2N)
.
The running time for Find will be O(N)
.
It seems such clear cut that Binary Search is superior to Find, why did the committee of C++ still have Find in the algorithm library?
I am sure the C++ committee had their reasons for including Find, what benefits of Find am I missing or how is Find superior to Binary Search?
EDITED : Changed running time of quicksort to NLog2N
Best Answer
Not every list is sorted, yet sometimes there are things we'd like to find.
Also quicksort is
O(n log n)
, which means it takes longer thanO(n)
.