CC-5 : Implement Ternary Search Algorithm.

Description:

The Ternary search algorithm works on sorted lists. The algorithm checks and divides the input list into 3 lists (ternary/three lists) recursively and searches for the element within the partitioned sub list till the required element is found, or the conclusion is reached that the element does not exist in the sorted list. Since the original input list is sorted, if the element to be searched is lesser than the element at which the list is being partitioned, we need to search in the lower partition only and vice versa. Given an input array and an element to be searched, search the required element in the input array using Ternary search.

Test cases and expected outputs:

Input Parameters	Expected outputs
Array: 3, 22, 44, 67, 77, 96, 122, 144, 201,	122 found at index 6 76 found at index -1 3 found at index 0 201 found at index 8

Pseudocode:

ternarySearch(nums[], startIdx, endIdx, toSearch):

Integer array named nums, and integer named toSearch to be searched are received as input parameters. Integer variables named startIdx and endIdx, which mark the start and end indices of nums to be searched in current recursive call are also received as input parameters.

If (startIdx <= endIdx) do the following steps:

Set integer variable oneThirdIdx to (startIdx+ (startIdx-endIdx)/3), we will use this variable to check the index of first partition in which are searching for required integer.

Set integer variable twoThirdIdx to (endIdx-(startIdx-endIdx)/3), we will use this variable to check the middle index of partition in which are searching for required integer.

The third partition will start from twoThirdIdx to length of input array.

If nums[oneThirdIdx]==toSearch, return oneThirdIdx, as we have found the index of the number that we were searching for.

If nums[twoThirdIdx]==toSearch, return twoThirdIdx, as we have found the index of the number that we were searching for.

If (toSearch < nums[oneThirdIdx]) :

We need to search in first partition, so recursively call ternarySearch(nums[], startIdx, oneThirdIdx-1, toSearch).

If (toSearch > nums[twoThirdIdx]) :

We need to search in first partition, so recursively call ternarySearch(nums[], twoThirdIdx+1, endIdx, toSearch).

Return value returned from recursively calling ternarySearch(nums[], oneThirdIdx +1, twoThirdIdx-1, toSearch).

If toSearch is not found in code above return -1, as the required element does not exist within the input array.

Code:

public int ternarySearch(int[] nums, int startIdx, int endIdx, int toSearch){
	if (startIdx <=  endIdx) {
	int oneThirdIdx=startIdx+ ((endIdx-startIdx)/3);
	int twoThirdIdx=endIdx-((endIdx-startIdx)/3);
	if (nums[oneThirdIdx]==toSearch) {
		return oneThirdIdx;
	}
	if (nums[twoThirdIdx]==toSearch) {
		return twoThirdIdx;
	}
	if (toSearch < nums[oneThirdIdx]) {
		return ternarySearch(nums,startIdx,oneThirdIdx-1, toSearch);
	}
	if (toSearch > nums[twoThirdIdx]) {
		return ternarySearch(nums,twoThirdIdx+1,endIdx, toSearch);
	} 
	return ternarySearch(nums,oneThirdIdx+1,twoThirdIdx-1, toSearch);	
	}
	return -1;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class SearchTernarySearch {

public int ternarySearch(int[] nums, int startIdx, int endIdx, int toSearch){
	if (startIdx <=  endIdx) {
	int oneThirdIdx=startIdx+ ((endIdx-startIdx)/3);
	int twoThirdIdx=endIdx-((endIdx-startIdx)/3);
	if (nums[oneThirdIdx]==toSearch) {
		return oneThirdIdx;
	}
	if (nums[twoThirdIdx]==toSearch) {
		return twoThirdIdx;
	}
	if (toSearch < nums[oneThirdIdx]) {
		return ternarySearch(nums,startIdx,oneThirdIdx-1, toSearch);
	}
	if (toSearch > nums[twoThirdIdx]) {
		return ternarySearch(nums,twoThirdIdx+1,endIdx, toSearch);
	} 
	return ternarySearch(nums,oneThirdIdx+1,twoThirdIdx-1, toSearch);	
	}
	return -1;
}


public static void main(String[] args) {
	/************************
	 Test cases given below:
	 **********************/
	int retVal;
	try {
	
	SearchTernarySearch search=new SearchTernarySearch();
	int[] nums= { 3,22,44,67,77,96,122, 144, 201};
	int toSearch=122;
	retVal=search.ternarySearch(nums,0, nums.length-1, toSearch);
	
	System.out.println("\nArray:");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < nums.length; arrayIndex++) {
		System.out.print(nums[arrayIndex]+", ");		
	} 
	
	System.out.println("\n\n"+toSearch + " found at index "+ retVal);	
	
	toSearch=76;
	retVal=search.ternarySearch(nums,0, nums.length-1, toSearch);
	System.out.println("\n"+toSearch + " found at index "+ retVal);	
	
	toSearch=3;
	retVal=search.ternarySearch(nums,0, nums.length-1, toSearch);
	System.out.println("\n"+toSearch + " found at index "+ retVal);	
	
	toSearch=201;
	retVal=search.ternarySearch(nums,0, nums.length-1, toSearch);
	System.out.println("\n"+toSearch + " found at index "+ retVal);	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}



}