0

We now that binary search exists, which takes log2(n) time. But is it possible to have a base three search where you divide the parts of a search subarray into 3 parts instead of two, and if possible, would it be log3(n) time?

If that is true, then why aren't base 4 and higher searches used either?

Icecap
  • 1
  • 3
  • 1
    What should that achieve? You know the basic assumption of binary-search? Weak-ordering, which is a *binary* relation! (thats a bit informal but should get you going) (that being said, the other comment mentioning ternary-search is also important in some cases; e.g. 1d-minimization; but that's something else) – sascha Oct 26 '17 at 01:14
  • 1
    Binary-3 is called "ternary". It is used for something else, though. – Sergey Kalinichenko Oct 26 '17 at 01:14
  • 1
    Yes, but as @sascha implies, most use cases are inherently binary, like sorting. If you can find a way to split things in more ways, then you could. https://en.m.wikipedia.org/wiki/K-ary_tree?wprov=sfla1 – Gibryon Bhojraj Oct 26 '17 at 01:20
  • 1
    It would be log3(n) time counted in iterations, but each iteration takes two comparisons, so it takes more comparisons in total, which usually means it takes longer. The only bright side is that you can do the two comparisons for each iteration in parallel, so if the synchronization overhead doesn't kill you and you have threads available you might still save on elapsed time. – mcdowella Oct 26 '17 at 04:28

0 Answers0