Ternary search is a divide-and-conquer algorithm that can be used to search for a specific element in a sorted array. It works by dividing the array into three parts, rather than two (as in binary search), and then determining which part to search next based on the value of the target element.

Java Implementation

public class TernarySearch {

    /**
     * Performs a ternary search on a sorted array.
     * 
     * @param arr    The sorted array to search in.
     * @param left   The starting index of the current search range.
     * @param right  The ending index of the current search range.
     * @param key    The value to search for.
     * @return The index of the key if found, otherwise -1.
     */
    public static int ternarySearch(int[] arr, int left, int right, int key) {
        if (right >= left) {
            // Divide the array into three parts
            int partitionSize = (right - left) / 3;
            int mid1 = left + partitionSize;
            int mid2 = right - partitionSize;

            // Check if key is present at any mid
            if (arr[mid1] == key) {
                return mid1;
            }
            if (arr[mid2] == key) {
                return mid2;
            }

            // Since key is not found at mid1 or mid2, determine which segment to search
            if (key < arr[mid1]) {
                return ternarySearch(arr, left, mid1 - 1, key); // Search in the left segment
            } else if (key > arr[mid2]) {
                return ternarySearch(arr, mid2 + 1, right, key); // Search in the right segment
            } else {
                return ternarySearch(arr, mid1 + 1, mid2 - 1, key); // Search in the middle segment
            }
        }
        return -1; // Key not found
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int key = 7;
        int result = ternarySearch(arr, 0, arr.length - 1, key);

        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array.");
        }
    }
}
    

Program Structure

• TernarySearch Class: This is the main class that contains the implementation of the ternary search algorithm.
• ternarySearch Method:
  • Parameters:
    • int[] arr: The sorted array in which we are searching for the key.
    • int left: The starting index of the current search range.
    • int right: The ending index of the current search range.
    • int key: The element we are searching for.
  • Returns: The index of the key if found, otherwise -1.
  • Logic:
    • The array is divided into three parts using two midpoints.
    • The method checks if the key matches any of the midpoints.
    • Based on the comparison, it recursively searches in the relevant segment.
• main Method: This is the entry point of the program where the array is initialized and the search method is called.

Conclusion

The ternary search algorithm is a useful technique for searching in sorted arrays. Although it is less commonly used than binary search due to its increased complexity, it can be beneficial in specific scenarios where dividing the array into three parts is advantageous.