Consider an ordered array A of size n and the following ternary search algorithm
ID: 672234 • Letter: C
Question
Consider an ordered array A of size n and the following ternary search algorithm for finding the index i such that A[i] = K.
Divide the array into three parts. If A[n/3] > K, the first third of the array is searched recursively, else if A[2n/3] > K then the middle part of the array is searched recursively, else the last third of the array is searched recursively. Provisions are also made in the algorithm to return n/3 if A[n/3] = K, or return 2n/3 if A[2n/3]=K.
Write the recurrence relation for the number of comparisons C(n) in the average case for the binary and ternary searches and solve the ternary average case only.
Do the following experiment (need to write a program in the language of your choice):
Generate arrays of sizes n = 500, 1000, 2000, 4000 and 8000. Fill the arrays as follows:
A[i] = integer(); i=0,1,2, …, n-1.
Generate random integer numbers between 0 and (8*sqrt(n)), and search each array for acquired random number using binary search and ternary search.
Record the number of comparison for each array and for each of the two searches.
Repeat Steps 2 and 3, ten (10) times. Take the average number of comparisons for the 10 runs, for each array and each search method.
Present the results in the form of graph or table, etc. (your choice). Compare the binary search with the ternary search in term of the number of operations needed for the search. How do these result match your findings in (a) ? Write one paragraph conclusions
Explanation / Answer
Hi,
Below is the solution to your question:
Explaination:
The following is recursive formula for counting comparisons in worst case of Binary Search.
The following is recursive formula for counting comparisons in worst case of Ternary Search.
Program in java:
/**
** Java Program to Implement Ternary Search Algorithm and Binary search algorithm
**/
import java.util.Scanner;
import java.util.Random;
Public class BinarySearch
{
public static int binarySearch( int[] A, int value, int start, int end)
{
int start=0
int end=length - 1;
int mid;
while( start<=end)
{
mid = ( start+end)/2;
if( value<a[mid])high=mid-1;
else if( value>a[mid])low=mid+1;
else
return mid;
}
return -1;
}
}
/** Class TernarySearch **/
public class TernarySearch
{
/** call function **/
public static int ternarySearch (int[] A, int value)
{
return ternarySearch(A, value, 0, A.length - 1);
}
/** TernarySearch function **/
public static int ternarySearch (int[] A, int value, int start, int end)
{
if (start > end)
return -1;
/** First boundary: add 1/3 of length to start **/
int mid1 = start + (end-start) / 3;
/** Second boundary: add 2/3 of length to start **/
int mid2 = start + 2*(end-start) / 3;
if (A[mid1] == value)
return mid1;
else if (A[mid2] == value)
return mid2;
/** Search 1st third **/
else if (value < A[mid1])
return ternarySearch (A, value, start, mid1-1);
/** Search 3rd third **/
else if (value > A[mid2])
return ternarySearch (A, value, mid2+1, end);
/** Search middle third **/
else
return ternarySearch (A, value, mid1,mid2);
}
/** Main method **/
public static void main(String[] args)
{
Scanner scan = new Scanner( System.in );
System.out.println("Ternary Search Test ");
int n, i;
/** Accept number of elements **/
System.out.println("Enter number of integer elements");
n = scan.nextInt();
/** Create integer array on n elements **/
int arr[] = new int[ n ];
/** Accept elements **/
System.out.println(" Enter "+ n +" sorted integer elements");
for (i = 0; i < n; i++)
arr[i] = scan.nextInt();
Random rand;
int key=rand.nextint(0,8*sqrt(n));
int result = binarySearch(arr,key);
int result1= ternarySearch(arr, key);
if (result == -1)
System.out.println(" "+ key +" element not found");
else
System.out.println(" "+ key +" element found at position "+ result);
}
}
Hope that helps...HAPPY ANSWERING!!!!!!!