Ternary search is a searching algorithm that searches an element in a sorted array.
Algorithm
Ternary search works similar to Binary search. The only difference is instead of dividing the array into 2 parts, the array is divided into three parts and 2 parts are rejected on each iteration. That is, the array is reduced to 1/3 of its size on every iteration.
Steps
- Let X be the value we wish to search for.
- We use 2 variables start and end to mark the beginning index and ending index of the given array.
- Repeat the following steps while start<=end.
- We calculate 2 mids, mid1 and mid2
mid1 = (end-start)/3 + start
mid2 = 2*(end-start)/3 + start
The array is now divided into 3 parts,- [start,mid1]
- [mid1,mid2]
- [mid2,end]
- If X is equal to arr[mid1] or arr[mid2], we return the index of X and terminate the program.
- If X lies in interval [start,mid1), set end = mid1 – 1.
- If X lies in the interval (mid1,mid2), set start = mid1 + 1 and end = mid2 – 1.
- Else X lies in the interval (mid2,end], set start = mid2 + 1.
- We calculate 2 mids, mid1 and mid2
- If X is not present in the array, return -1.

Ternary Search without Recursion
Pseudo Code
Assuming the array is sorted in increasing(ascending order) order.
arr: Array we want to search
x: value we want to search in arr
Integer Ternary_Search( arr , x )
start := 0
end := arr.LENGTH - 1
WHILE start <= end DO
mid1 := (end - start)/3 + start
mid2 := 2*(end - start)/3 + start
IF x == arr[mid1] THEN
return mid1
ELSE IF x == arr[mid2] THEN
return mid2
ELSE IF x < arr[mid1] THEN
end := mid1 - 1
ELSE IF x < arr[mid2] THEN
start := mid1 + 1
end := mid2 - 1
ELSE
start := mid2 + 1
END ELSEIF
END WHILE
return -1
END FUNCTION
Code
#include<stdio.h> int ternary_search(int arr[], int n, int x) { int start = 0; int end = n - 1; int mid1; int mid2; while (start <= end) { int mid1 = (end - start) / 3 + start; int mid2 = 2 * (end - start) / 3 + start; if (x == arr[mid1]) { return mid1; } else if (x == arr[mid2]) { return mid2; } else if (x < arr[mid1]) { end = mid1 - 1; } else if (x < arr[mid2]) { start = mid1 + 1; end = mid2 - 1; } else { start = mid2 + 1; } } return -1; } int main() { int arr[] = { 2,3,5,7,10,10,11,15,17,20,25,30,32,36,40 }; int n = 15; int index; int x; printf("Enter element you want to search: "); scanf("%d", &x); index = ternary_search(arr, n, x); if (index != -1) { printf("%d%s%d", x, " is present at index ", index); } else { printf("%d%s", x, " is not present in the given array\n"); } }
Output
Enter element you want to search: 17
17 is present at index 8
Ternary Search with recursion
Pseudo Code
arr: Array we want to search
x: value we want to search in arr
N: size of array
Integer Ternary_Search( arr , x , start , end )
WHILE start <= end DO
mid1 := (end - start)/3 + start
mid2 := 2*(end - start)/3 + start
IF x == arr[mid1] THEN
return mid1
ELSE IF x == arr[mid2] THEN
return mid2
ELSE IF x < arr[mid1] THEN
return Ternary_Search( arr , x , start , mid1 - 1 )
ELSE IF x < arr[mid2] THEN
return Ternary_Search( arr , x , mid1 + 1 , mid2 - 1 )
ELSE
return Ternary_Search( arr , x , mid2 + 1 , end )
END ELSEIF
END WHILE
return -1
END FUNCTION
Code
#include<stdio.h> int ternary_search(int arr[], int x, int start, int end) { int mid1; int mid2; if (start <= end) { int mid1 = (end - start) / 3 + start; int mid2 = 2 * (end - start) / 3 + start; if (x == arr[mid1]) { return mid1; } else if (x == arr[mid2]) { return mid2; } else if (x < arr[mid1]) { return ternary_search(arr, x, start, mid1 - 1); } else if (x < arr[mid2]) { return ternary_search(arr, x, mid1 + 1, mid2 - 1); } else { return ternary_search(arr, x, mid2 + 1, end); } } return -1; } int main() { int arr[] = { 2,3,5,7,10,10,11,15,17,20,25,30,32,36,40 }; int n = 15; int index; int x; printf("Enter element you want to search: "); scanf("%d", &x); index = ternary_search(arr, x, 0, n - 1); if (index != -1) { printf("%d%s%d", x, " is present at index ", index); } else { printf("%d%s", x, " is not present in the given array\n"); } }
Output
Enter element you want to search: 32
32 is present at index 12
Time Complexity
- It is clear that on each iteration, array is reduced to 1/3 of it’s size.
- In worst case, the value X is not present in the array.
- The program will terminate when start becomes less than end, that is the size of array becomes 0.
Now, let N be the size of the array
- After the first iteration
Size of array = N/3 - After the second iteration
Size of array = N/32
…..
….. - After the Kth iteration
Size of array = N/3k
The problem will terminate when N/3k = 1
N/3k = 1 N = 3k k = log3(N)
The worse case requires K iterations.
Hence, the time complexity is O(log3(N)).
Time Complexity using recurrence relation
The array is reduced to 1/3 of it’s size on every iteration. Thus, the recurrence relation of Ternary search is
T(N) = T(N/3) + C
where C is the constant
T(N) = T(N/3) + C …1 T(N/3) = T(N/32) + C …2 T(N/32) = T(N/33) + C …3 ..... ..... T(9) = T(3) + C …k-1 T(3) = T(1) + C …k On adding equation 1 to k, we get T(N) = T(1) + k*C We can observe that, N/3k = 1 k = log3(N) T(N) = T(1) + log3(N)*C Since T(1) and C are constants, we can ignore them T(N) = log3(N)
Hence, the time complexity is O(log3(N))
References
https://en.wikipedia.org/wiki/Binary_search_algorithm