Exponential Search is a fast and efficient algorithm designed to locate elements in sorted arrays. It combines the speed of binary search with a smart way of quickly finding a search range. Instead of checking each element one by one, Exponential Search first finds a range where the target could exist by repeatedly doubling an index. Once the range is found, it applies Binary Search within that range. For beginners learning TypeScript, this algorithm is a great way to understand how combining different strategies can improve efficiency.
with hands-on learning.
get the skills and confidence to land your next move.
This search technique is particularly useful for large datasets where the target is likely to be near the beginning. By narrowing down the search space quickly, Exponential Search can outperform linear search significantly. Understanding this algorithm helps beginners practice loops, conditionals, recursion, and binary search concepts while learning how to optimize searches in real-world scenarios.
Program 1: Iterative Exponential Search
This program demonstrates the standard iterative Exponential Search, finding the target efficiently by doubling the search index.
function binarySearch(arr: number[], target: number, left: number, right: number): number {
while (left <= right) {
let mid = left + Math.floor((right - left) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
function exponentialSearch(arr: number[], target: number): number {
if (arr[0] === target) return 0;
let i = 1;
while (i < arr.length && arr[i] <= target) {
i = i * 2;
}
return binarySearch(arr, target, Math.floor(i / 2), Math.min(i, arr.length - 1));
}
let data: number[] = [1, 3, 5, 7, 9, 11, 13, 15];
let targetValue: number = 9;
console.log("Element found at index:", exponentialSearch(data, targetValue));This program first finds the range where the target could exist by doubling the index and then performs a binary search within that range. Beginners can see how combining two search strategies improves efficiency over linear search.
Program 2: Recursive Exponential Search
Recursion can also implement Exponential Search, allowing the algorithm to find the range and perform binary search recursively.
function binarySearchRecursive(arr: number[], target: number, left: number, right: number): number {
if (left > right) return -1;
let mid = left + Math.floor((right - left) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) return binarySearchRecursive(arr, target, mid + 1, right);
else return binarySearchRecursive(arr, target, left, mid - 1);
}
function exponentialSearchRecursive(arr: number[], target: number, i: number = 1): number {
if (arr[0] === target) return 0;
if (i >= arr.length || arr[i] > target) {
return binarySearchRecursive(arr, target, Math.floor(i / 2), Math.min(i, arr.length - 1));
}
return exponentialSearchRecursive(arr, target, i * 2);
}
let numbers: number[] = [2, 4, 6, 8, 10, 12, 14];
let searchValue: number = 12;
console.log("Element found at index:", exponentialSearchRecursive(numbers, searchValue));This recursive approach is elegant and demonstrates how dividing the problem into smaller steps can make searching more structured and efficient.
Program 3: Exponential Search for Negative Numbers
Exponential Search works with negative numbers in sorted arrays without any modification.
function binarySearch(arr: number[], target: number, left: number, right: number): number {
while (left <= right) {
let mid = left + Math.floor((right - left) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
function exponentialSearch(arr: number[], target: number): number {
if (arr[0] === target) return 0;
let i = 1;
while (i < arr.length && arr[i] <= target) {
i = i * 2;
}
return binarySearch(arr, target, Math.floor(i / 2), Math.min(i, arr.length - 1));
}
let negatives: number[] = [-50, -40, -30, -20, -10, 0, 10];
let targetNegative: number = -20;
console.log("Element found at index:", exponentialSearch(negatives, targetNegative));Beginners can understand that the doubling mechanism and binary search still work for negative numbers since comparisons behave the same way.
Program 4: Exponential Search for Floating Point Numbers
This program demonstrates Exponential Search for decimal values in sorted arrays.
function binarySearch(arr: number[], target: number, left: number, right: number): number {
while (left <= right) {
let mid = left + Math.floor((right - left) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
function exponentialSearch(arr: number[], target: number): number {
if (arr[0] === target) return 0;
let i = 1;
while (i < arr.length && arr[i] <= target) {
i = i * 2;
}
return binarySearch(arr, target, Math.floor(i / 2), Math.min(i, arr.length - 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:", exponentialSearch(decimals, targetDecimal));This shows that the algorithm is versatile and works effectively with floating point numbers, making it suitable for many numerical datasets.
Program 5: Exponential Search for Large Arrays
Exponential Search is very efficient for large arrays due to its rapid range detection.
function binarySearch(arr: number[], target: number, left: number, right: number): number {
while (left <= right) {
let mid = left + Math.floor((right - left) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
function exponentialSearch(arr: number[], target: number): number {
if (arr[0] === target) return 0;
let i = 1;
while (i < arr.length && arr[i] <= target) {
i = i * 2;
}
return binarySearch(arr, target, Math.floor(i / 2), Math.min(i, arr.length - 1));
}
let largeArray: number[] = Array.from({length: 1000}, (_, i) => i * 2);
let targetLarge: number = 800;
console.log("Element found at index:", exponentialSearch(largeArray, targetLarge));Even with a thousand elements, the algorithm quickly finds the target by jumping exponentially to find the range, then applying binary search. This demonstrates how Exponential Search combines speed and precision.
Program 6: Exponential Search for Duplicate Values
Exponential Search can locate any occurrence of a target in an array with duplicates.
function binarySearch(arr: number[], target: number, left: number, right: number): number {
while (left <= right) {
let mid = left + Math.floor((right - left) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
function exponentialSearch(arr: number[], target: number): number {
if (arr[0] === target) return 0;
let i = 1;
while (i < arr.length && arr[i] <= target) {
i = i * 2;
}
return binarySearch(arr, target, Math.floor(i / 2), Math.min(i, arr.length - 1));
}
let duplicates: number[] = [5, 10, 10, 15, 20, 20, 25];
let targetDuplicate: number = 20;
console.log("Element found at index:", exponentialSearch(duplicates, targetDuplicate));Beginners can see that while it may return any occurrence of the target, it still finds the element efficiently without scanning each item sequentially.
Program 7: Exponential Search in Uniform Data
This program applies Exponential Search to a uniformly spaced sorted array.
function binarySearch(arr: number[], target: number, left: number, right: number): number {
while (left <= right) {
let mid = left + Math.floor((right - left) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
function exponentialSearch(arr: number[], target: number): number {
if (arr[0] === target) return 0;
let i = 1;
while (i < arr.length && arr[i] <= target) {
i = i * 2;
}
return binarySearch(arr, target, Math.floor(i / 2), Math.min(i, arr.length - 1));
}
let uniformData: number[] = [10, 20, 30, 40, 50, 60, 70];
let targetUniform: number = 40;
console.log("Element found at index:", exponentialSearch(uniformData, targetUniform));This highlights that Exponential Search works effectively across evenly spaced or non-uniformly spaced datasets as long as they are sorted.
Frequently Asked Questions (FAQ)
Exponential Search can raise common beginner questions:
Q1. Can Exponential Search work on unsorted arrays?
No, the array must be sorted for the search to be correct.
Q2. How is Exponential Search different from Binary Search?
It first quickly finds a search range by doubling the index and then applies Binary Search, making it faster for targets near the start.
Q3. Can Exponential Search handle negative numbers and decimals?
Yes, it works with any numeric data in sorted arrays.
Q4. Is Exponential Search suitable for large datasets?
Yes, it finds the range quickly and performs binary search efficiently, making it ideal for large arrays.
Q5. Does Exponential Search always return the first occurrence of a duplicate?
No, it may return any occurrence; additional logic is needed to find the first or last occurrence.
Conclusion
Exponential Search is an efficient and versatile algorithm for searching sorted arrays. In this article, we explored TypeScript programs implementing Exponential Search using iteration, recursion, negative numbers, decimals, duplicates, and large datasets. Each example demonstrated how the algorithm quickly identifies the search range and then applies Binary Search to locate the target.
Beginners can learn from these examples how combining search strategies can optimize performance and reduce comparisons. Practicing Exponential Search in TypeScript builds a strong foundation for understanding more advanced searching techniques and helps you write faster, more efficient code for real-world applications.
