Write a recursive ternary search algorithm that splits the array into three parts instead of the two parts used by a binary search.

Question

What will be an ideal response?

Answer 1

```
public static int trinarySearch(int data[], int target){
return trinarySearch(data, target, 0, data.length-1);
}

//Uses trinary search to search for target in a[first] through
//a[last] inclusive. Returns the index of target if target
//is found. Returns -1 if target is not found.
public static int trinarySearch(int data[], int target,
int first, int last) {
int result;
if (first > last)
result = -1;
else {
int mid1 = (2*first + last)/3;
int mid2 = (first + 2*last)/3;
if (target == data[mid1])
result = mid1;
else if (target == data[mid2])
result = mid2;
else if (target < data[mid1])
result = trinarySearch(data, target, first, mid1 - 1);
else if (target < data[mid2])
result = trinarySearch(data, target, mid1 + 1, mid2-1);
else
result = trinarySearch(data, target, mid2 + 1, last);

}
return result;
}

```

This code is in Methods.java.