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
is not present in the array, return -1.**X**

### 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/3^{2}

…..

….. - After the Kth iteration

Size of array = N/3^{k}

The problem will terminate when N/3^{k} = 1

N/3^{k}= 1 N = 3^{k}k = log_{3}(N)

The worse case requires K iterations.

Hence, the time complexity is **O( log_{3}(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/3^{2}) + C …2 T(N/3^{2}) = T(N/3^{3}) + 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/3^{k}= 1 k = log_{3}(N) T(N) = T(1) + log_{3}(N)*C Since T(1) and C are constants, we can ignore them T(N) = log_{3}(N)

Hence, the time complexity is **O( log_{3}(N))**

## References

https://en.wikipedia.org/wiki/Binary_search_algorithm