Why Binary Search is Preferred over Ternary Search?

Binary search and Ternary search algorithms are used to search an element in a sorted array. Binary search reduces the array by 1/3 on each iteration whereas Ternary search reduced array size by 1/3 on each iteration.

The Time complexity of Binary Search is log2(N).
The Time complexity of Ternary Search is log3(N).

Ternary search should be faster than the Binary search since log2(N) >= log3(N) but this is not the case. When we calculate the Time complexity of any algorithm, we generally ignore the constants. But the constants in Ternary search are relatively larger than Binary search. Due to this, the Ternary search is slower.

Proof

\\*For\;Binary\;Search,\;T_b(N) = C_b*log_2(N)\hfill\hfill...1\newline\\*For\;Ternary\;Search,\;T_t(N) = C_t*log_3(N)\hfill...2\newline\\*Using\;the\;property\;log_b(N) = \dfrac{log_e(N)}{log_e(b)}\; in\;equation\;1 \;and\; equation\; 2,\\*we\; get\newline\\*T_b(N) = C_b*\dfrac{log_e(N)}{log_e(2)} = \dfrac{C_b}{log_e(2)}*log_e(N) = 1.4426*C_b*log_e(N)\hspace*{\fill}...3\newline\newline\\*T_t(N) = C_t*\dfrac{log_e(N)}{log_e(3)} = \dfrac{C_t}{log_e(3)}*log_e(N) = 0.9102*C_t*log_e(N)\hfill...4

Cb = Number of Comparision in each iteration of Binary Search = 2
Ct = Number of Comparision in each iteration of Ternary Search = 4

Substituting Cb and Ct in equation 3 and 4, we get

\\*T_b(N) = 1.4426*2*log_e(N) = 2.885*log_e(N)\hfill..5\newline\\*T_t(N) = 0.9102*4*log_e(N) = 3.6408*log_e(N)\hfill...6

On Comparing equation 5 and 6,

\\*T_b(N) < T_t(N)

Thus, we can say that Binary search is faster than Ternary search.

This happens because of the increase in the number of comparisons in Ternary search. In simple words, the reduction in the number of iterations in Ternary search is not able to compensate for the increase in comparisons.
Hence, Binary search algorithm is preferred over the Ternary search.

References

https://en.wikipedia.org/wiki/Binary_search_algorithm

Leave a Comment

Your email address will not be published. Required fields are marked *