Ternary Search is an efficient searching algorithm that is similar to Binary Search, but instead of splitting the array into two halves, it divides the array into three parts. This allows the algorithm to potentially find a target element faster in certain situations. Like Binary Search, Ternary Search works only on sorted arrays and uses a divide-and-conquer approach to reduce the number of comparisons.
with hands-on learning.
get the skills and confidence to land your next move.
For beginners, Ternary Search is a great way to understand how algorithms can be optimized by dividing the problem into multiple parts. It is particularly useful when you want to minimize comparisons in large datasets or when dealing with mathematical functions in optimization problems. Learning Ternary Search also strengthens problem-solving skills and helps beginners become comfortable with recursion and iterative approaches in JavaScript.
Program 1: Iterative Ternary Search
This program demonstrates a basic iterative Ternary Search on a sorted array.
function ternarySearchIterative(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid1 = left + Math.floor((right - left) / 3);
let mid2 = right - Math.floor((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;
}
let numbers = [1, 3, 5, 7, 9, 11, 13];
let target = 7;
let result = ternarySearchIterative(numbers, target);
console.log(result !== -1 ? `Element found at index ${result}` : "Element not found");This program works by dividing the array into three segments and checking two middle points. Beginners can think of it as “splitting into thirds instead of halves and narrowing the search range.” It is useful for reducing the number of comparisons compared to Linear Search, especially for large arrays.
Program 2: Recursive Ternary Search
This version demonstrates Ternary Search using recursion.
function ternarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
if (left > right) return -1;
let mid1 = left + Math.floor((right - left) / 3);
let mid2 = right - Math.floor((right - left) / 3);
if (arr[mid1] === target) return mid1;
if (arr[mid2] === target) return mid2;
if (target < arr[mid1]) return ternarySearchRecursive(arr, target, left, mid1 - 1);
else if (target > arr[mid2]) return ternarySearchRecursive(arr, target, mid2 + 1, right);
else return ternarySearchRecursive(arr, target, mid1 + 1, mid2 - 1);
}
let values = [2, 4, 6, 8, 10, 12, 14];
let searchTarget = 10;
let resultRecursive = ternarySearchRecursive(values, searchTarget);
console.log(resultRecursive !== -1 ? `Element found at index ${resultRecursive}` : "Element not found");This recursive approach works by repeatedly dividing the array into thirds and calling the function on the relevant segment. Beginners can understand recursion as “repeating the same search on smaller sections.” It is useful for understanding divide-and-conquer strategies beyond Binary Search.
Program 3: Ternary Search for first occurrence
This program modifies Ternary Search to find the first occurrence of a target value in a sorted array with duplicates.
function ternarySearchFirst(arr, target, left = 0, right = arr.length - 1) {
let result = -1;
while (left <= right) {
let mid1 = left + Math.floor((right - left) / 3);
let mid2 = right - Math.floor((right - left) / 3);
if (arr[mid1] === target) {
result = mid1;
right = mid1 - 1;
} else if (arr[mid2] === target) {
result = mid2;
right = mid2 - 1;
} else if (target < arr[mid1]) right = mid1 - 1;
else if (target > arr[mid2]) left = mid2 + 1;
else {
left = mid1 + 1;
right = mid2 - 1;
}
}
return result;
}
let duplicates = [1, 2, 2, 2, 3, 4, 5];
let targetDup = 2;
console.log("First occurrence index:", ternarySearchFirst(duplicates, targetDup));This program works by continuing to search the left segment even after finding the target. Beginners can think of it as “keep looking left to find the first match.” It is useful for arrays containing duplicates.
Program 4: Ternary Search for last occurrence
This example demonstrates finding the last occurrence of a target using Ternary Search.
function ternarySearchLast(arr, target, left = 0, right = arr.length - 1) {
let result = -1;
while (left <= right) {
let mid1 = left + Math.floor((right - left) / 3);
let mid2 = right - Math.floor((right - left) / 3);
if (arr[mid1] === target) {
result = mid1;
left = mid1 + 1;
} else if (arr[mid2] === target) {
result = mid2;
left = mid2 + 1;
} else if (target < arr[mid1]) right = mid1 - 1;
else if (target > arr[mid2]) left = mid2 + 1;
else {
left = mid1 + 1;
right = mid2 - 1;
}
}
return result;
}
let data = [5, 7, 7, 7, 8, 9, 10];
let targetValue = 7;
console.log("Last occurrence index:", ternarySearchLast(data, targetValue));This program works by continuing the search in the right segment to find the last index. Beginners can think of it as “keep looking right to find the last match.” It is useful for counting duplicates or ranges in sorted arrays.
Program 5: Ternary Search as a reusable function
This program wraps Ternary Search into a reusable function for multiple datasets.
function ternarySearchUtility(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid1 = left + Math.floor((right - left) / 3);
let mid2 = right - Math.floor((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;
}
let numbersSet = [3, 6, 9, 12, 15, 18];
let findNum = 12;
let resultUtility = ternarySearchUtility(numbersSet, findNum);
console.log(resultUtility !== -1 ? `Element found at index ${resultUtility}` : "Element not found");This reusable function allows beginners to efficiently search any sorted array using Ternary Search. It demonstrates good coding practices, such as modularity and clarity, while leveraging algorithm efficiency.
Frequently Asked Questions (FAQ)
This section answers common beginner questions about Ternary Search in JavaScript.
Q1. What is Ternary Search?
Ternary Search is a searching algorithm that divides a sorted array into three parts and checks two midpoints to efficiently find a target element.
Q2. Can Ternary Search be used on unsorted arrays?
No, Ternary Search requires a sorted array to work correctly.
Q3. How is Ternary Search different from Binary Search?
Binary Search splits the array into two halves, while Ternary Search divides it into three parts, potentially reducing comparisons.
Q4. What is the time complexity of Ternary Search?
The time complexity is O(log3 n), which is similar to Binary Search but with three-way division.
Q5. Why should beginners learn Ternary Search?
It teaches an advanced divide-and-conquer approach, recursion, and helps understand optimization techniques in searching algorithms.
Conclusion
Ternary Search is a powerful algorithm that divides a sorted array into three parts, offering an efficient alternative to Binary Search in certain scenarios.
By practicing iterative, recursive, and first/last occurrence implementations, beginners can gain a deep understanding of divide-and-conquer strategies and improve their algorithmic thinking. Ternary Search strengthens skills in recursion, iterative logic, and modular programming in JavaScript, preparing learners for more advanced algorithmic challenges.
