# Ternary Search

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

1. Let X be the value we wish to search for.
2. We use 2 variables start and end to mark the beginning index and ending index of the given array.
3. Repeat the following steps while start<=end.
1. 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]
2. If X is equal to arr[mid1] or arr[mid2], we return the index of X and terminate the program.
3. If X lies in interval [start,mid1), set end = mid1 – 1.
4. If X lies in the interval (mid1,mid2), set start = mid1 + 1 and end = mid2 – 1.
5. Else X lies in the interval (mid2,end], set start = mid2 + 1.
4. 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