0

I wish to search for an integer in a vector of integer. I have two candidates for the job:

  1. Binary Search

  2. Find

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

  • 2
    -1, you changed your wrong statement about the running time of quicksort by an edit, which obviously makes your assumption pointless that "Binary Search is superior to Find". Honestly, when I would have noticed such an error in a question of mine, I would immediately retract the question. – Doc Brown Feb 9 '14 at 16:12
  • 1
    @DocBrown worth noting that asker of the question has no way to "retract" it when it has got upvoted answers - and this is just the case here, starting with the fastest gun kind one that merely qualifies as a comment – gnat Feb 9 '14 at 16:43
  • @DocBrown Yea I have no way to retract the question once an answer has been given , anyway my question is still valid as NlogN is quicker than N , stackoverflow.com/questions/962545/… , I believe i dont deserve the downvote – Computernerd Feb 9 '14 at 16:50
  • 2
    @Computernerd: You misunderstood the answers to that linked SO question. An O(NlogN) algorithm can be faster than an O(N) one, but that all depends on the constants and non-dominant factors that are ignored by Big-O notation. In this case, the "sort+binary search" will most likely loose out to the linear search unless you are searching a lot on the same sorted sequence. – Bart van Ingen Schenau Feb 9 '14 at 17:41
  • @Computernerd: N*(log N) is larger than N for N beeing sufficiently large (since log N is larger than 1 for N beeing larger than the base of the logarithm). Nevertheless an "O(NlogN)" algorithm can be faster than an O(N) algorithm in some special cases, but don't expect a one-short Quick-Sort + Binary Search to be faster than a "Find" for any real-world library implementation. – Doc Brown Feb 9 '14 at 19:14
7

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 than O(n).

  • 1
    @ U2ZEF1 not really , stackoverflow.com/questions/962545/… – Computernerd Feb 9 '14 at 13:43
  • 1
    No, quicksort is not O(n log n), it is O(n^2)! O(n log n) is the average complexity of quicksort (in number of comparisons). – Tamás Szelei Feb 9 '14 at 14:10
  • @fish Sure. There's still no way it's beating linear find. The confusion stems from the (now edited) question stating quicksort was O(log(n)). – U2EF1 Feb 9 '14 at 21:03
6

Keep in mind that from a theoretical perspective it's impossible to let sorting and finding be quicker than finding. To sort, you need to look at every element at least once to determine its place. To find, in the worst case scenario, you need to look at every element once (provided they are not sorted). Only when you're doing repeated searches, it may make sense to sort the elements first (a "startup fee") to have "cheaper" searches after that.

  • Even better, if it's common for your sought-after element to exist, linear find will only look at half the list on average. Sorting still has to look at everything. – U2EF1 Feb 9 '14 at 21:12
  • @U2EF1 Only under certain conditions (e.g. random distribution of the elements). Anyway, such details are not very important for the theoretical argument I wanted to make. :) – Thijs van Dien Feb 10 '14 at 19:23
2

As others have said, binary search provides you with a high performance solution when your data is sorted, while find is slower but does not have that presorted constraint.

In addition it is important to note that to sort a vector you must either copy it and mutate it or simply mutate it. This is not only expensive but has side effects which may not match the semantics of your algorithm.

Additionally C++11 defines the new collections std::unordered_set and std::unordered_map which are by definition not compatible with binary search algorithms.

0

Find is meant to operate on any generic STL container, some of which are expensive to sort. There are faster ways to find an item with the right data structure, such as with std::set, and that class has a find member function.

Furthermore, the premise of your question is false. The asymptotic complexity of quicksort is O(n^2), not O(log 2n) or O(n log n). Many people seem to confuse that with the average complexity of quicksort.

Quicksort, or partition-exchange sort, is a sorting algorithm developed by Tony Hoare that, on average, makes O(n log n) comparisons to sort n items. In the worst case, it makes O(n^2) comparisons, though this behavior is rare.

  • 2
    The asymptotic complexity of quicksort is Θ(n log n) ... in the average case. The asymptotic complexity of quicksort is Θ(n²) ... in the worst case. Both statements are correct and important, and generally both bounds should be given. It's silly to claim one case is the case that matters and the other should, if mentioned at all, be hidden behind further qualification. There is no distinction between "average complexity" and "asymptotic complexity", that wouldn't even make sense. – user7043 Feb 9 '14 at 14:16
  • @delnan Asymptotic complexity talks about worst case complexity, unless stated otherwise, and that is what Big-O is, function that is an upper bound to another (again, look it up if you don't believe me). The average case complexity of quicksort is O(n log n). You are using theta instead of omicron, which means a different thing: tight bounds, both upper and lower. – Tamás Szelei Feb 10 '14 at 7:43
  • Can you give a citation? Asymptotic complexity just means the limit of some function as n -> infinity. That function can be the time taken or number of operations in the worst case (and this is indeed the most common, so this is sometimes left unstated). But other important (sometimes more important) measures are the time taken in the average case, the space used in the worst case, the space used in the average case, or the count of a certain operation (e.g. the comparison in functions). And the theta vs. omicron thing is completely orthogonal: ... – user7043 Feb 10 '14 at 10:35
  • ... It expresses how you bound the function in question, not which function you bound. For example, you can say the worst-case time of linear search is in O(n³) because it's asymptotically less than cn³, but a more precise bound would be O(n), and an even more precise one would be Θ(n), which *also states that it isn't actually better than linear. Big Oh is often (misleadingly) used when we have tight bounds, but it's also useful when you haven't figured out the exact bound yet or can't be bothered to ("the worst-case time complexity is at most linear, maybe better"). – user7043 Feb 10 '14 at 10:40
  • @delnan citation: "A further tacit assumption is that the worst case analysis of computational complexity is in question unless stated otherwise" link – Tamás Szelei Feb 10 '14 at 14:29
0

Besides what was mentioned, even given an array that was already sorted, if it has, say, just a measly 10 elements in it, the linear-time search is likely to strongly outperform the logarithmic-time binary search. Algorithmic complexity doesn't equate to speed. It describes scalability, but scalability isn't so useful on inputs that don't scale.

Besides that a binary search is less generalized and less applicable, since it requires random-access iterators which linked structures generally can't provide. A sequential search only requires forward iterators which practically any data structure can provide.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.