Ternary Search is an advanced searching algorithm designed to find an element in a sorted array more efficiently than Linear Search. Unlike Binary Search, which divides the search space into two halves, Ternary Search splits it into three parts at each step. This allows it to narrow down the target’s location faster, especially in large datasets. For beginners learning TypeScript, Ternary Search provides a great opportunity to understand both recursion and divide-and-conquer strategies.
with hands-on learning.
get the skills and confidence to land your next move.
The algorithm is useful in applications where quick searches are needed in sorted collections, such as searching in dictionaries, leaderboards, or large numerical datasets. Learning Ternary Search also strengthens your understanding of algorithmic thinking, array manipulation, and how efficient searching can improve program performance. By implementing this in TypeScript, beginners can see how logical partitioning of data can make searches faster and more structured.
Program 1: Iterative Ternary Search
This program demonstrates a standard iterative approach to Ternary Search, dividing the array into three parts and checking the target in each segment.
function ternarySearchIterative(arr: number[], target: number): number {
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 data: number[] = [2, 4, 6, 8, 10, 12, 14];
let targetValue: number = 10;
console.log("Element found at index:", ternarySearchIterative(data, targetValue));This program shows how splitting the array into three segments helps locate the target more efficiently than checking every element. Beginners can visualize it as zooming in on the correct segment while skipping unnecessary comparisons.
Program 2: Recursive Ternary Search
Recursion provides a natural way to implement Ternary Search, reducing the search space at each recursive call.
function ternarySearchRecursive(arr: number[], target: number, left: number = 0, right: number = arr.length - 1): number {
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 numbers: number[] = [1, 3, 5, 7, 9, 11, 13];
let searchValue: number = 7;
console.log("Element found at index:", ternarySearchRecursive(numbers, searchValue));This recursive approach is elegant and shows beginners how divide-and-conquer strategies break a problem into smaller parts until the target is found.
Program 3: Ternary Search for Negative Numbers
Ternary Search works naturally with negative numbers in a sorted array.
function ternarySearchIterative(arr: number[], target: number): number {
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 negatives: number[] = [-50, -40, -30, -20, -10, 0, 10];
let targetNegative: number = -20;
console.log("Element found at index:", ternarySearchIterative(negatives, targetNegative));Beginners can see that no extra steps are needed to handle negative values, making the algorithm flexible for all numerical datasets.
Program 4: Ternary Search for Floating Point Numbers
This program demonstrates that Ternary Search can also locate decimal values in a sorted array.
function ternarySearchIterative(arr: number[], target: number): number {
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 decimals: number[] = [0.5, 1.0, 1.5, 2.0, 2.5, 3.0];
let targetDecimal: number = 2.0;
console.log("Element found at index:", ternarySearchIterative(decimals, targetDecimal));Beginners can see that the comparison logic works the same way for floating point numbers, making Ternary Search versatile for various data types.
Program 5: Ternary Search for Large Arrays
Ternary Search performs efficiently in large arrays by cutting down the search space quickly.
function ternarySearchRecursive(arr: number[], target: number, left: number = 0, right: number = arr.length - 1): number {
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 largeArray: number[] = Array.from({length: 1000}, (_, i) => i * 2); // 0, 2, 4, ..., 1998
let targetLarge: number = 800;
console.log("Element found at index:", ternarySearchRecursive(largeArray, targetLarge));Even with a thousand elements, the algorithm finds the target quickly because it repeatedly divides the array into three smaller segments, demonstrating its efficiency for beginners learning algorithm optimization.
Program 6: Ternary Search for Duplicate Values
Ternary Search can locate any occurrence of a target in arrays with repeated values.
function ternarySearchIterative(arr: number[], target: number): number {
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 duplicates: number[] = [5, 10, 10, 15, 20, 20, 25];
let targetDuplicate: number = 20;
console.log("Element found at index:", ternarySearchIterative(duplicates, targetDuplicate));Beginners can observe that the search finds a target efficiently without scanning the entire array sequentially, even in the presence of duplicates.
Program 7: Ternary Search in Uniform Data
This program shows Ternary Search applied to uniformly distributed data, highlighting its divide-and-conquer strength.
function ternarySearchRecursive(arr: number[], target: number, left: number = 0, right: number = arr.length - 1): number {
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 uniformData: number[] = [10, 20, 30, 40, 50, 60, 70];
let targetUniform: number = 40;
console.log("Element found at index:", ternarySearchRecursive(uniformData, targetUniform));Beginners can understand that Ternary Search works best on sorted arrays, regardless of spacing between elements, as long as the comparisons are valid.
Frequently Asked Questions (FAQ)
Ternary Search raises common questions for beginners:
Q1. Can Ternary Search be used on unsorted arrays?
No, the array must be sorted for the algorithm to work correctly.
Q2. Is Ternary Search faster than Binary Search?
It can be slightly faster because it divides the array into three parts instead of two, but both have logarithmic complexity.
Q3. Can Ternary Search handle negative numbers and decimals?
Yes, it works naturally with all numeric types in sorted arrays.
Q4. Does Ternary Search always return the first occurrence of a duplicate?
No, it may return any occurrence; special logic is needed to find the first or last occurrence.
Q5. Is Ternary Search suitable for large datasets?
Yes, it efficiently reduces search space and performs well for large arrays.
Conclusion
Ternary Search is a powerful and efficient algorithm for searching sorted arrays. In this article, we explored TypeScript programs implementing Ternary Search using iteration, recursion, negative numbers, decimals, duplicates, and large datasets. Each example illustrated how dividing the array into three segments helps locate the target faster and with fewer comparisons.
By practicing these examples, beginners can understand the advantages of divide-and-conquer algorithms and learn how to optimize search operations in TypeScript. Mastering Ternary Search provides a solid foundation for exploring more advanced search techniques and writing efficient, clean, and optimized code for real-world applications.
