Abstract—This
document describes the algorithm “ternary search” to search an element in a
pre-sorted array in logarithmic time.
I. INTRODUCTION
THIS document describes the algorithm “ternary
search”. It consists of core algorithm, methods i.e. recursive and iterative,
C-like pseudo code, time complexity analysis, comparison of ternary search algorithm
with binary search algorithm and various results derived from executing the
algorithm.
II.
Core Algorithm
The ternary search algorithm is inspired by the
binary search algorithm. In ternary search algorithm the array is divided into
3 equal parts. It is checked if the element to search is in range of any one
part. If the element is in any one of that part the range of the search is
decreased to the range of that part. By repeatedly calling this procedure we
can narrow down the range to 3 or less number of elements. After the number of
elements in a range is 3 or less we can search linearly in this range as
further dividing the range of 3 is a little costly and it becomes hard to
handle the edge cases scenario in recursive method.
For implementation of this algorithm in different programming languages please checkout my Git repository: https://github.com/VrajPandya/TernarySearch
For implementation of this algorithm in different programming languages please checkout my Git repository: https://github.com/VrajPandya/TernarySearch
A.
Recursive method
Below is the recursive algorithm/ pseudo code
for ternary search.
int ternary_search_rec (int
arr, int key, int start, int end)
{
// simple initializations
int dif = end - start;
int one_third;
int i;
//terminating conditions
if(start > end || key
< arr[start] || key > arr[end]) return -1;
if(dif<=3){
// perform a linear search
for(i=start; i <= end; i++)
if(arr[i]== key)
return i;
return -1;
}
else{
one_third = dif/3;
// check if the element is this range
if(key >= arr[start] && key <= arr[start + one_third]
){
//check if the element is found
if(key== arr[start]) return start;
if(key == arr[start + one_third]) return start +
one_third;
// recursion
return t_search(arr, key , start + 1, start +
one_third - 1);
} else
// check if the element is this range
if(key >= arr[start + one_third] &&
key <= arr[end - one_third] ) {
//check if the element is found
if(key == arr[start + one_third]) return start +
one_third;
if(key == arr[end - one_third]) return end -
one_third;
// recursion
return t_search(arr, key , start + one_third +
1, end - one_third - 1);
} else
//the element is in the final range
{
//check if the element is found
if(key == arr[end - one_third]) return end -
one_third;
if(key == arr[end]) return end;
// recursion
return t_search(arr, key, end - one_third + 1,
end - 1);
}
}
B.
Iterative method
Below is the iterative method algorithm/pseudo
code for ternary search.
int t_search_itr(int*
arr, int key, int size)
{
// simple initializations
int start=0, end = size;
int dif, one_third, i;
// check if the key is
in range
if(start > end || key
< arr[start] || key > arr[end]) return -1;
dif = end - start;
while(dif>3)
{
one_third = dif / 3;
//check if the key is in range
if(key >= arr[start] && key <= arr[start + one_third]
){
//check
if the element is found
if(key== arr[start]) return start;
if(key == arr[start + one_third])
return start + one_third;
//make
readjustments in the range
start = start + 1;
end
= start + one_third -1;
} else if(key >= arr[start + one_third] &&
key <= arr[end - one_third] ) {
//check
if the element is found
if(key
== arr[start + one_third]) return start + one_third;
if(key
== arr[end - one_third]) return end - one_third;
//make
readjustments in the range
start = start +
one_third + 1;
end
= end - one_third - 1;
} else {
//check if the
element is found
if(key
== arr[end - one_third]) return end - one_third;
if(key
== arr[end]) return end;
//make
readjustments in the range
start
= end - one_third + 1;
end
= end - 1;
}
dif = end - start;
}
// perform a linear
search
for(i=start;i<=end;i++)
if(arr[i]==key)
return i;
return -1;
}
III.
Complexity analysis
The time complexity analysis of the ternary
search is almost same as binary search as in both the algorithm the range of
search gets divided by 2 or 3. The analysis done over here is for the iterative
method. The analysis for the recursive method is almost the same because there
are only a few changes in the number of constants which does not affect the
final time complexity.
There are 7 comparison operations, 1 division
operation, 6 addition or subtractions. Total of 14 operations.
We will assume the time for addition and subtraction
is same.
Assume time for a comparison c, time for
division is d, time for addition or subtraction is a
Let us examine the operations for a specific
case, where the number of elements in the array n is 6561. In this case let us
also assume that the element to search is one of the worst case situation for
the ternary search.
When n= 6561 the iteration reduces size to n=2187
When n= 2187 the iteration reduces size to n=729
When n= 729 the iteration reduces size to n=243
When n= 243 the iteration reduces size to n=81
When n= 81 the iteration reduces size to n=27
When n= 27 the iteration reduces size to n=9
When n= 9 the iteration reduces size to n=3
After that, simple linear search is called and
the index of the element is returned.
Thus we see that ternary Search is iterated 7
times for n = 6561.
Note that
6561 = 38 = 37+1
Now, let us consider a more general case where n
is still a power of 3. Let us say n = 3k.
Following the above argument for 6561 elements,
it is easily seen that after k-1 searches, the while loop is executed k times
and n reduces to size 3. Let us assume
that each run of the while loop involves at most 14 operations (1). Thus total number of operations: 14(k-1).Now for very large k let us assume
k = k-1 because of the linear search done at the end of the algorithm. The
value of k can be determined from the expression
3k = n
Taking log3 of both sides
k = log3 (n)
Thus total number of operations = 14 * log3
(n)
Now total time taken by the operations is
(7c + d + 6a) * log3 (n)
Now for the Big-O time complexity analysis we ignore the constants.
So, O(log3
n)
Hence, the time complexity of the ternary search
is O(log3n).
IV.
Comparison
The ternary search algorithm is a way faster algorithm
than the binary search algorithm. The progression of ternary search is much
faster than binary search. The time complexity analysis method is also the same
for both the algorithms. The idea behind both the algorithm is divide and conquer.
Here is the comparison between ternary search and
binary search.
Number
of search
|
Ternary
search
|
Binary
Search
|
10000000
|
62
|
2297
|
50000000
|
297
|
11537
|
100000000
|
618
|
25153
|
400000000
|
2479
|
106697
|
The comparison of binary and ternary search running the stated
number of searches. The time is in milliseconds.
Effectively optimizes the time complexity and thus highly preferable over binary search when input data set is very large.
ReplyDelete