Question

• Problem 2:

There are no data errors that need to be checked as all the data will be assumed correct. You can use the array of the previous example to test your program, however, I

suggest that you also use other input arrays to validate the correctness and efficiency of your solution. • Your program MUST be submitted only in source code form (.java file).

Write a program in Java to implement a recursive search functionint terSearch(int A[], int l, int r, int x)

that returns the location of x in a given sorted array of n integers A if x is present, otherwise -1.

The terSearch search function, unlike the binary search, must consider two dividing points

int d1 = l + (r - l)/3

int d2 = d1 + (r - l)/3

For the first call of your recursive search function terSearch you must consider l = 0 and r = A.length - 1.

Important Notes:

• For this problem you must add the main method in your program in order to test your implementation.

• There are no data errors that need to be checked as all the data will be assumed correct.

• Your program MUST be submitted only in source code form (.java file).

• A program that does not compile or does not run loses all correctness points.

Answer 1

For ternary search, everything remains the same as binary search, except two mid values are calculated according to the formula and increased checking conditions to update range of array to be searched. Range limits updation is explained in the program.

import java.util.*;

class Main
{
   // recursive function
   static int terSearch(int A[], int l, int r, int x) {
       if(l>r) // base condition, x not found
           return -1;
          
       // d1 and d2 calculation
       int d1 = l + (r-l)/3;
       int d2 = d1 + (r-l)/3;
      
       // decreasing the limits of array according to conditions
       if(x<A[d1]) {
           return terSearch(A, l, d1-1, x); // r=d1-1
       } else if(x==A[d1]){
           return d1;   // element at d1
       } else if(x>A[d1] && x<A[d2]) {
           return terSearch(A, d1+1, d2-1, x); //l=d1+1, r=d2-1
       } else if(x==A[d2]) {
           return d2;   // element at d2
       } else { // x>A[d2]
           return terSearch(A, d2+1, r, x);   //l=d2-1
       }
   }
  
   public static void main (String[] args)
   {
       Scanner sc = new Scanner(System.in);
       int n, x, foundIndex;
       System.out.println("Enter array size");
       n = sc.nextInt();   // array size input
       int A[] = new int[n];
       System.out.println("Enter array elements");
       for(int i=0;i<n;i++) {
           A[i] = sc.nextInt();   // array elements input
       }
       System.out.println("Enter element to be searched");
       x = sc.nextInt();
       foundIndex = terSearch(A,0,n-1,x);   // call the ternary search function
       if(foundIndex==-1)   // x not found
           System.out.println(x + " not found");
       else
           System.out.println(x + " found at index(starting from 0): "+foundIndex);
   }
}

Sample Code Run: