customizing binary search

Question

In binary search we divide the array into 2 and then, we search inside an individual array again by using binary search recursively.

Now, instead of binary search, if I use a ternary search, the search will divide the array into 3. My questions are:

• Will be the ternary search faster than the binary search or vice versa?
• Under what condition which algorithm it will perform better?
• Does performance depends on size of array?

Answer 1

From the Wiki's, a ternary search tree is a ternary tree where the nodes are in order with respect to the search keys. If the search keys are strings, each node stores a single character and searching for a string consists of a series of binary searches, one for each character in the string:

In binary search you just compare and get one half or the other.
But, in a ternary search where you compare,if it is less than, you get 1st 1/3rd, else again compare if less than, you get the second 1/3rd or else get the last 1/3rd.

Read more here :

• Why use binary search if there's ternary search?
• Why binary search instead of triple(3 parts) search ?

Answer 2

Well, it depends what you mean by "faster", exactly. Asymptotically speaking, they both run in O(log n) time (technically, binary search runs in O(log_2(n)) while ternary search runs in O(log_3(n)) where log_k means "log base k"; however, these only differ by a constant factor so they're both equivalent to O(log n)). So from an algorithms standpoint, these two functions run in the same amount of time overall (i.e., they have the same time complexity).

That said, there are certainly particular case where one will take less computation than the other. For example, if the target value is exactly in the middle of the array, binary search will return the value upon the first iteration and not ever recurse while ternary would have to recurse to find the value. Similarly, if the target value is exactly one-third of the way through the array, ternary search will find it immediately while binary search will have to recurse.

Answer 3

If you're talking about a single-processor system, then there's no asymptotic difference and there's more overhead with a ternary search. On multiprocessor/multicore systems, it will (up to a point) speed up the search to divide it into independent searches (provided the execution environment/language allows such a division). But this is usually best done at the top level only once.

Answer 4

I'm having a bit of trouble determining what you mean by "ternary search." The reason that binary search splits the array into two halves is that each comparison you make partitions the array into two regions, elements less than the element in consideration and elements greater than the element in consideration. I don't see an easy way to generalize this so that you split the array into three pieces by doing a single comparison.

However, if you don't split the array into equal halves and instead break it up into a ¹/₃ / ²/₃ split on each iteration, then you will still get O(lg n) performance, though the constant term will be higher. In fact, for any constant ε in which you split the array into fractions of size ε / 1-ε pieces, you will get O(lg n) behavior.

If when performing the comparison you split the array into two pieces of size εn and (1-ε)n, terminating only when the array size becomes less than one, then the algorithm will terminate after k steps, where k is the smallest integer for which ε^kn < 1 and for which (1-ε)^kn < 1. Rearranging, we get

ε^kn < 1

ε^k < 1/n

k > log_ε 1/n

k > - log_ε n

k > - lg n / lg ε

k > lg n / lg ¹/_ε

Using similar logic but with 1 - ε, we get that

k > lg n / lg ¹/_{(1 - ε)}

Notice that since lg ¹/_ε and lg ¹/_{(1 - ε)} are constants, the smallest k satisfying these properties is O(lg n).

Answer 5

Think of it in this way, binary search leverages one moving pointer (mid) to get to the base case. If you put more pointers in the search space, in each loop you'll decrease the search space to a smaller - that is more definite size but increase the time to take the decision as to which is the next search space.

At each step of a binary search algorithm, 1/2 of search space is discarded using a simple if-else block, for ternary search algorithm it will discard 2/3 of the search space using a bit more complex if-elseif-else block.If I propose a N-ary search algorithm for the same, it will discard (N - 1)/N of the search space (leaving only 1/N ie the destination), theoretically have a constant time complexity - but with a very ugly if-elseif-elseif-elseif-...(N - 1 times)...elseif-else block.

Basically, it is a tradeoff between the number of times the while loop is executed V/S the time it takes to execute the loop block a single time! Hope you get the idea.

In terms of big O notation:
O(log(2)N) -> (binary search)
O(log(3)N) -> (ternary search)
...
...
O(log(N)N) -> (proposed N-ary search) essentially O(1), but this is just the number of times the loop runs, and hides the time it takes to execute each loop which is also an important factor.
I made a practical complexity function using the formula (time to execute one iteration) * (number of iteration). which asserts that binary search is in-fact the simplest and fastest overall. This is however a debatable approximation as to what factors to take into account.

red is binary search, blue is ternary and green is 10-ary search approximation on the reference graph