Question

How to implement ternary search to find a value in a sorted list with TypeScript

Answer 1

function ternarySearch(l: number, r: number, key: number, arr: number[]): number {
    while (l <= r) {
        const mid1 = l + Math.floor((r - l) / 3);
        const mid2 = r - Math.floor((r - l) / 3);

        if (arr[mid1] === key) return mid1;
        if (arr[mid2] === key) return mid2;

        if (key < arr[mid1]) {
            r = mid1 - 1;
        } else if (key > arr[mid2]) {
            l = mid2 + 1;
        } else {
            l = mid1 + 1;
            r = mid2 - 1;
        }
    }

    return -1; // not found
}

function main(): void {
    const arr: number[] = [1, 2, 8, 14, 15, 64, 78, 89, 99, 100, 110, 123];
    const toSearch = 89;

    const index = ternarySearch(0, arr.length - 1, toSearch, arr);

    if (index !== -1) {
        console.log(`Element found at index: ${index}`);
    } else {
        console.log("Element not found.");
    }
}

main();



/*
run:

"Element found at index: 7" 

*/

 

70+ SQL courses for beginners and professionals