48
$\begingroup$

Searching an array of $N$ elements using binary search takes, in the worst case $\log_2 N$ iterations because, at each step we trim half of our search space. If, instead, we used 'ternary search', we'd cut away two-thirds of our search space at each iteration, so the worst case should take $\log_3 N < \log_2 N$ iterations...

It seems that ternary search is faster, so why do we use binary search?

$\endgroup$
  • 3
    $\begingroup$ Couldn't one use the same reasoning about Quaternary search? Or even decimal search... or anything larger than 2. $\endgroup$ – d'alar'cop Sep 8 '14 at 13:28
  • 4
    $\begingroup$ please read about B+Trees $\endgroup$ – arunmoezhi Sep 8 '14 at 18:46
  • 5
    $\begingroup$ Linear search often is faster than binary search on small-to-medium-sized problems on modern hardware, because it's cache-coherent and almost all branches are predicted correctly. $\endgroup$ – Pseudonym Sep 9 '14 at 2:47
  • 2
    $\begingroup$ Also 2*log_3(N) = log_3(N^2) if it speaks to your intuition. $\endgroup$ – PawelP Sep 9 '14 at 17:32
  • 6
    $\begingroup$ Let's put this into intuitive terms. If using a 3-based search is faster because it cuts the search space more at each iteration, then isn't using a million-based search faster? But you can easily see that on average you'd have to do 500,000 checks inside each iteration to determine the 1-millionth slice that contained the target. Clearly, cutting the search space in half each iteration and no more, gives you the most information in a single step, reliably. $\endgroup$ – ErikE Sep 10 '14 at 2:58
76
$\begingroup$

If you apply binary search, you have $$\log_2(n)+O(1)$$ many comparisons. If you apply ternary search, you have $$ 2 \cdot \log_3(n) + O(1)$$ many comparisons, as in each step, you need to perform 2 comparisons to cut the search space into three parts. Now if you do the math, you can observe that: $$ 2 \cdot \log_3(n) + O(1) = 2 \cdot \frac{\log(2)}{\log(3)} \log_2(n)+ O(1) $$ Since we know that $2 \cdot \frac{\log(2)}{\log(3)} > 1$, we actually get more comparisons with ternary search.

By the way: $n$-ary search may make a lot of sense in case if comparisons are quite costly and can be parallelized, as then, parallel computers can be applied.

Note that argument can be generalized to $n$-ary search quite easily. You just need to show that the function $f(k) = (k-1) \cdot \frac{\log(2)}{\log(k)}$ is strictly monotone increasing for integer values of $k$.

$\endgroup$
  • 1
    $\begingroup$ And LHS is linear & RHS is logarithmic so it won't help for any quaternary or something more than that .... Nice Explanations.... Thanks $\endgroup$ – The Mean Square Sep 8 '14 at 13:37
  • 3
    $\begingroup$ Just for the sake of completeness: note that an abstract measure like the number of element comparisons may or may not dominate actual runtime. In particular, you might have to consider how many cache misses you are likely to get on long arrays with either search. (Here, they coincide. I'm just noting this because the OP asks, "why is it faster?", and answering that with an abstract measure can be misleading for some algorithms.) $\endgroup$ – Raphael Sep 8 '14 at 16:07
  • 10
    $\begingroup$ In a ternary search, 1/3 of the time you will only need 1 comparison (do lower comparison: if in the lower third, you don't need the second comparison). That makes ternary only about 5% slower instead of 25% (in this world in which we only care about comparison count). I'm not sure how to generalize this to n-ary, although I suspect it never gets faster than binary. $\endgroup$ – Aaron Dufour Sep 8 '14 at 17:22
  • 2
    $\begingroup$ @AaronDufour: Since one could do a quaternary search by comparing to the middle item first and then ignoring the result of the other comparisons, the only way quaternary search could be faster would be if three comparisons could be done in parallel more cheaply than two comparisons could be performed sequentially. $\endgroup$ – supercat Sep 8 '14 at 18:38
  • 1
    $\begingroup$ @AaronDufour But you are amortizing over elements to search for, and it is not clear to me why that is ok. In the worst case both comparisons may be performed at every step. $\endgroup$ – Sasho Nikolov Sep 9 '14 at 5:51
26
$\begingroup$

DCTLib is right, but forget the math for a second.

By your logic then, n-ary should be the fastest. But if you think about it, n-ary is exactly equal to a regular iteration search (just iterating through the list 1 by 1, but in reverse order). First you select the last (or next to last) item in the list and compare that value to your comparison value. Then you remove that item from your list, and then choose the last item in the new list, which is just the next to last value in the array. Each time, you would only be eliminating 1 value at a time until you found your value.

Instead, you should think about it like this - how do I eliminate the most values from the list each iteration? In a binary search, you always eliminate half the list. In a ternary search, there is a possibility (33.33% chance, actually) that you can eliminate 2/3 of the list, but there is an even greater chance (66.66%) that you will only eliminate 1/3 of the list. in order to calculate O(n), you need to look at the worst case scenario, which is 1/3, less than 1/2. As you get closer and closer to n, it gets even worse.

Not only will the worst case scenario be improved with binary search, but your average time will be improved as well. Looking at expected value (what portion of the list can we remove on average), we use this formula:

(P_lower)x(portion we can remove if lower)+(P_higher)x(portion we can remove if higher) = E

For binary search, this is .5x.5 + .5x.5 = .5 (we always remove half the list). For ternary searches, this value is .666x.333 + .333x.666 = 0.44, or at each step, we will likely only remove 44% of the list, making it less efficient than the binary search, on average. This value peaks at 1/2 (half the list), and decreases the closer you get to n (reverse iteration) and 0 (regular iteration).

Ok, so I lied..there's a little math involved, but I hope that helps!

$\endgroup$
  • 1
    $\begingroup$ This is a great answer. $\endgroup$ – The_Sympathizer Dec 22 '15 at 4:28
  • $\begingroup$ Ya boundary analysis helps understand hard math ! n-ary sequential search has the same cost of linear search O(n) . $\endgroup$ – shuva Oct 26 '18 at 19:06
-2
$\begingroup$

Please note the log(N) vs 2 log(N) comparisons argument is based on a naive interpretation of the algorithm. If I were to actually sit down and write this in x86 assembly the results would be inverted. The problem is the use of integers for test cases combined with an insufficiently smart compiler that can't remove the redundant comparisons. Retry with strings and an appropriate string comparison function, and code it to call the comparison function once per loop and you will find the ternary search is faster again.

$\endgroup$
  • 2
    $\begingroup$ Of course ternary search would be faster if you could do it with only one comparison per iteration. But, no matter if strings or integers, you can't. $\endgroup$ – FrankW Sep 9 '14 at 17:16
  • $\begingroup$ The comparisons would not be redundant and the problem has nothing to do with the compiler. In order to divide the search space into three parts, you need 2 comparisons. In a binary search, you need only compare to the middle element and you then know which half of the search space the result would lie in. With ternary search, you'd need to compare with the element 1/3 of the way through the list AND the one 2/3 of the way through the list. What type of data you're comparing or what language you're using is irrelevant. Granted, if the item is in the 1st 3rd, you could stop after 1 comparison. $\endgroup$ – reirab Sep 9 '14 at 18:06
  • 2
    $\begingroup$ On some platforms, ternary search could be faster due to allowing the CPU more time to fetch the operands from RAM before needing them for comparison. But that depends totally on the platform used and its latencies and caches. $\endgroup$ – jpa Sep 10 '14 at 12:48
  • 1
    $\begingroup$ Darn it -- wrong definition of ternary search. $\endgroup$ – Joshua Sep 22 '14 at 15:39

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.