Ternary

Ternary search is a divide-and-conquer algorithm used for finding the position of a specific value within an array, especially when the array is sorted.

pseudocode:

function ternary_search(array, left, right, target):
    while left <= right:
        # Calculate mid1 and mid2
        mid1 = left + (right - left) / 3
        mid2 = right - (right - left) / 3

        # Check if target is at mid1 or mid2
        if array[mid1] == target:
            return mid1
        if array[mid2] == target:
            return mid2

        # If target is smaller than mid1, search the left third
        if target < array[mid1]:
            right = mid1 - 1
        # If target is larger than mid2, search the right third
        elif target > array[mid2]:
            left = mid2 + 1
        # If target is between mid1 and mid2, search the middle third
        else:
            left = mid1 + 1
            right = mid2 - 1

    # If target is not found
    return -1

It's similar to binary search, but instead of dividing the array into halves, it divides it into thirds.

function ternarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        let mid1 = Math.floor(left + (right - left) / 3);
        let mid2 = Math.floor(right - (right - left) / 3);

        if (arr[mid1] === target) {
            return mid1;
        }

        if (arr[mid2] === target) {
            return mid2;
        }

        if (target < arr[mid1]) {
            right = mid1 - 1;
        } else if (target > arr[mid2]) {
            left = mid2 + 1;
        } else {
            left = mid1 + 1;
            right = mid2 - 1;
        }
    }

    return -1; // Target not found
}

// Example usage:
const array = [1, 3, 5, 7, 9, 11, 13, 15, 17];
const target = 11;
const index = ternarySearch(array, target);
console.log("Index of", target, ":", index);

In this example, the ternarySearch function takes an array arr and a target value target as input and returns the index of the target value if found, or -1 if not found.

The algorithm divides the array into three parts (mid1, mid2) and compares the target value with elements at these two midpoints.

Depending on the comparison, it narrows down the search space by updating the left and right pointers.

This process continues until the target value is found or the search space is exhausted.