Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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$.
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}) \times \text{(portion we can remove if lower)} +(P_{higher}) \times \text{(portion we can remove if higher)} = E$
For binary search, this is $0.5 \times 0.5 + 0.5 \times 0.5 = 0.5$ (we always remove half the list). For ternary searches, this value is $0.666 \times 0.333 + 0.333 \times 0.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!
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.
