algorithmdata-structuresbinary-treeternary-tree

Why use binary search if there's ternary search?


I recently heard about ternary search in which we divide an array into 3 parts and compare. Here there will be two comparisons but it reduces the array to n/3. Why don't people use this much?


Solution

  • Actually, people do use k-ary trees for arbitrary k.

    This is, however, a tradeoff.

    To find an element in a k-ary tree, you need around k*ln(N)/ln(k) operations (remember the change-of-base formula). The larger your k is, the more overall operations you need.

    The logical extension of what you are saying is "why don't people use an N-ary tree for N data elements?". Which, of course, would be an array.