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/3²
  …..
  …..
• After the Kth iteration
  Size of array = N/3^k

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

N/3k = 1
N = 3k
k = log3(N)

The worse case requires K iterations.
Hence, the time complexity is O(log₃(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(log₃(N))

References

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