Question

Problem 2

Write a program in Java to implement a recursive search function int 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.

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

Answer 1

/**
* Main java program is to test themethodterSearch. In the main method, initialize the array with 10 elements in * *sorted order.Then call themethod ,terSearch Then print the results of seach method on console output.
* */
//Main.java
public class Main
{
   public static void main(String[] args)
   {  
       //initialize an array of integer values
       int A[]= {10,20,30,40,50,60,70,80,90,100};
       //Set target search ,x=100
       int x=100;

       //Set left most index,l=0
       int l=0;
       //Set the right most index,r which is size of the array
       int r=A.length-1;

       System.out.println("Searching for "+x);
       //calling method ,terSearch
       int result =terSearch(A, l, r, x);

       if(result!=-1)
           System.out.println(x+" element is found at index location : "+result);
       else
           System.out.println(x+" is not found.");

      
       //set x=500
       x=500;
       System.out.println("Searching for "+x);
       //calling method ,terSearch
       result =terSearch(A, l, r, x);

       if(result!=-1)
           System.out.println(x+" element is found at index location : "+result);
       else
           System.out.println(x+" is not found.");

   }

   /*The method terSearch takes four arguments :
   * An array of integer type, l for left most index, r for right most index
   * and x is the target element to search in the method.
   * The method returns -1 if the element x is not found
   * otherwise returns the index location of the element ,x found in the array*/
   public static int terSearch(int A[], int l, int r, int x)
   {
       /*Base -case */
       /*Returns -1 if the left most index,l is greater than right most index,r*/
       if ( l > r )
           return -1;

       /*Calculate the d1 and d2*/
       int d1 = l + ((r - l) / 3);
       int d2 = d1 + ((r - l) / 3);

       //Case-1:
       /*Checking element at index,d1 is equals to target element,x
       * then return,d1 value*/
       if (A[d1] == x)
           return d1;

       //Case-2:
       /*Checking element at index,d2 is equals to target element,x
       * then return,d2 value*/
       if (A[d2] == x)
           return d2;

       //Case-3:
       /*Checking if element,x is less than element at index,d1
       * then the call the recursive function terSearch in the range of l to d1-1 */
       if ( x < A[d1])
           return terSearch(A, l, d1 - 1, x);
       //Case-4:
       /*Checking if element,x is greater than element at index,d2
       * then the call the recursive function terSearch in the range of d2+1 to r */
       else if ( x > A[d2])
           return terSearch(A, d2 + 1, r, x);
       else
           //case-5:
           /*Otherwise the target element, x is in the range of d1 and d2 where d1 is left most index
           * and d2 is the right most index.
           * calling the method terSearch*/
           return terSearch(A, d1, d2, x);
   } //end of the method

} //end of the class

Sample Output:

Searching for 100
100 element is found at indexlocation : 9
Searching for 500
500 is not found.