Implement trinarySearch method.

The recursive trinarySearch method returns true or false depending if the element was found or not.

The trinarySearch method works in a similar manner to a binary search except it uses two mid values that divide the array into three portions. So, it needs to consider three recursive scenarios:

desired item is smaller than the element at index mid1

desired item is greater than the element at index mid2

desired item is smaller than the element at index mid2 but is greater than the element at index mid1

Utilize compareTo method, save the returned value(s) and use them in comparisons.

Use the following formulas to calculate mid indexes:

int mid1 = left + (right - left)/3;

int mid2 = right (right - left)/3;

import java.io.File; import java.io.FileNotFoundException; import java.io.IOException; import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class TrinarySearch { /** Task: Searches for a value in an array.  * @param a an array of Comparable objects  * @param desiredItem an item to search for  * @param n an integer > 0  */  public static > boolean trinarySearch(T[] a, T desiredItem, int n) { // it is assumed that the data is already sorted return trinarySearch(a, 0, n-1, desiredItem); } // end trinarySearch /** Task: recursive trinarySearch search through an array of objects.  * @param a an array of Comparable objects  * @param desiredItem an item to search for  * @param left an integer >= 0  * @param right an integer > left and < a.length  */   public static > boolean trinarySearch(T[] a, int left, int right, T desiredItem ) { // TODO Project 1   System.out.println("recursive trinarySearch method - IMPLEMENT ME"); 3 return false; } // end trinarySearch public static void main( String [ ] args ) { ArrayList accounts = new ArrayList<>( ); try { Scanner file = new Scanner( new File ("accounts.txt") ); while ( file.hasNext( ) ) // test for the end of the file { // read a line try { accounts.add( file.nextInt() ); } catch ( NumberFormatException nfe ) { System.out.println( "Error in input file ignoring" ); } } // release resources associated with flights.txt file.close( ); // print the accounts read System.out.println("Accounts are:"); for ( int index = 0; index < accounts.size(); index++ ) { System.out.println( "[" + index + "] " + accounts.get(index) ); } Integer[] accountsU = accounts.toArray(new Integer[accounts.size()]); Integer[] accountsS = Arrays.copyOf(accountsU, accountsU.length); Arrays.sort(accountsS); System.out.println("Sorted accounts are:"); for ( int index = 0; index < accountsS.length; index++ ) { System.out.println( "[" + index + "] " + accountsS[index] ); } boolean foundT = trinarySearch(accountsS, 7881200, accountsS.length); int foundB = Arrays.binarySearch(accountsS, 7881200); System.out.println(" trinarySearch: element 7881200 is found " + foundT); if (foundT && foundB >= 0 || !foundT && foundB < 0) System.out.println(" PASS"); else System.out.println(" FAIL"); foundT = trinarySearch(accountsS, 7881199, accountsS.length); foundB = Arrays.binarySearch(accountsS, 7881199); System.out.println(" trinarySearch: element 7881199 is found " + foundT); if (foundT && foundB >= 0 || !foundT && foundB < 0) System.out.println(" PASS"); else System.out.println(" FAIL"); foundT = trinarySearch(accountsS, 7881201, accountsS.length); foundB = Arrays.binarySearch(accountsS, 7881201); System.out.println(" trinarySearch: element 7881201 is found " + foundT); if (foundT && foundB >= 0 || !foundT && foundB < 0) System.out.println(" PASS"); else System.out.println(" FAIL"); foundT = trinarySearch(accountsS, 2222222, accountsS.length); foundB = Arrays.binarySearch(accountsS, 2222222); System.out.println(" trinarySearch: element 2222222 is found " + foundT); if (foundT && foundB >= 0 || !foundT && foundB < 0) System.out.println(" PASS"); else System.out.println(" FAIL"); foundT = trinarySearch(accountsS, 9999999, accountsS.length); foundB = Arrays.binarySearch(accountsS, 9999999); System.out.println(" trinarySearch: element 9999999 is found " + foundT); if (foundT && foundB >= 0 || !foundT && foundB < 0) System.out.println(" PASS"); else System.out.println(" FAIL"); foundT = trinarySearch(accountsS, 0000000, accountsS.length); foundB = Arrays.binarySearch(accountsS, 0000000); System.out.println(" trinarySearch: element 0000000 is found " + foundT); if (foundT && foundB >= 0 || !foundT && foundB < 0) System.out.println(" PASS"); else System.out.println(" FAIL"); foundT = trinarySearch(accountsS, 1111111, accountsS.length); foundB = Arrays.binarySearch(accountsS, 1111111); System.out.println(" trinarySearch: element 1111111 is found " + foundT); if (foundT && foundB >= 0 || !foundT && foundB < 0) System.out.println(" PASS"); else System.out.println(" FAIL"); foundT = trinarySearch(accountsS, 1005231, accountsS.length); foundB = Arrays.binarySearch(accountsS, 1005231); System.out.println(" trinarySearch: element 1005231 is found " + foundT); if (foundT && foundB >= 0 || !foundT && foundB < 0) System.out.println(" PASS"); else System.out.println(" FAIL"); foundT = trinarySearch(accountsS, 8777541, accountsS.length); foundB = Arrays.binarySearch(accountsS, 8777541); System.out.println(" trinarySearch: element 8777541 is found " + foundT); if (foundT && foundB >= 0 || !foundT && foundB < 0) System.out.println(" PASS"); else System.out.println(" FAIL"); System.out.println(" *** Done ***"); } catch ( FileNotFoundException fnfe ) { System.out.println( "Unable to find accounts.txt" ); } catch ( IOException ioe ) { ioe.printStackTrace( ); } } }

See sample run:

Accounts are:

[0] 5658845

[1] 8080152

[2] 1005231

[3] 4520125

[4] 4562555

[5] 6545231

[6] 7895122

[7] 5552012

[8] 3852085

[9] 8777541

[10] 5050552

[11] 7576651

[12] 8451277

[13] 7825877

[14] 7881200

[15] 1302850

[16] 1250255

[17] 4581002

Sorted accounts are:

[0] 1005231

[1] 1250255

[2] 1302850

[3] 3852085

[4] 4520125

[5] 4562555

[6] 4581002

[7] 5050552

[8] 5552012

[9] 5658845

[10] 6545231

[11] 7576651

[12] 7825877

[13] 7881200

[14] 7895122

[15] 8080152

[16] 8451277

[17] 8777541

trinarySearch: element 7881200 is found true

PASS

trinarySearch: element 7881199 is found false

PASS

trinarySearch: element 7881201 is found false

PASS

trinarySearch: element 2222222 is found false

PASS

trinarySearch: element 9999999 is found false

PASS

trinarySearch: element 0000000 is found false

PASS

trinarySearch: element 1111111 is found false

PASS

trinarySearch: element 1005231 is found true

PASS

trinarySearch: element 8777541 is found true

PASS

*** Done ***