CREATE OWN LIBRARY

Ternary search is a searching technique where it is searched that a particular element is present in the list or not. This searching technique is a little different from the binary search. In this technique, the list should be given in sorted order. First, the list is divided into three parts i.e. two middle values are calculated and the searched element is compared with the first middle value, if it is equal then the position is printed, otherwise, it is compared with the second middle value, if the value is equal then that position is printed. If both the middle values are unmatched, then it is checked whether the searched value is lesser than the first middle value, if it is lesser than the first middle value then only the first part will be checked for the element. If the searched element is greater than the 1st middle element and lesser than the 2nd middle element then the middle part of the array will be searched next, and if the searched element is greater than the 2nd middle element then the last part of the list will be searched. If the element is not found in the list, then a message “Element not found” will be shown. 

EXAMPLE:

Let the array be:

The array is in sorted order. Suppose the searching element is 82. Now for the first time in this case the lower index is 0, the upper index is 5 - 1 = 4(as the number of elements is 5). Now the middle values will be calculated as: 

mid1 = lower index + (upper index – lower index) / 3

        = 0 + (4-0)/3

        = 1

mid2 = upper index - (upper index – lower index) / 3

          = 4 – (4 - 0)/3

          = 4 – 1

          = 3

So, the array is now divided into three parts, one is from index 0 to 1, the middle part is from index 2 to 3 and the last part is from index 4 to 5.

Now, the searched element be 82. So, first, the searched element will be compared with the element of the index ‘mid1’ i.e. 1 here and the element is 68.

So, the elements are not matched. 

Now, the searched element will be compared with the element of index ‘mid2’ i.e. 3 here. The element at index 3 is 82 which is equal to the searched element. So, the position of the element will be printed.

INPUT: Array elements
OUTPUT: the index of the element if found
PROCESS:
Step 1: [taking the input]
	Read n [number of elements]
	For i=0 to n-1 repeat
		Read a[i]
	[end of ‘for’ loop]
	Read x [the element which is to be searched]
Step 2: [searching the element]
	Set l<-0
	Set u<-n-1
	While u≥l repeat 
		Set m1<-l+(u - l) / 3 
		Set m2<-u - (u - l) / 3
		if a[m1] =x then 
			Print "Element x is present at location m1”
			Set f<-1 
			break
		[End of ‘if’]
		if a[m2]= x then 
			Print "Element x is present at location m2”
			Set f<-1
			break
		[End of ‘if’]
		if x< a[m1] then  
			Set u <-m1 - 1 
		else if  x > a[m2] then 
			Set l<-m2 + 1 
		else 
 
			Set l <-m1 + 1 
			Set u<-m2 - 1 
		[End of ‘if’]
	[End of ‘while’ loop]
	If f=0 then 
		Print "Element not found"