Exponential Search Algorithm Code Implementations
Complete Exponential Search Algorithm code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read Exponential Search Algorithm Guide ยท Launch Interactive Visualizer
C++ Implementation
// Exponential Search Implementation in C++
#include <iostream>
#include <vector>
#include <functional>
class ExponentialSearch {
public:
static int exponentialSearch(const std::vector<int>& arr, int target) {
int n = arr.size();
if (n == 0) return -1;
// If array has only one element
if (n == 1) {
return arr[0] == target ? 0 : -1;
}
// Find range for binary search
int i = 1;
while (i < n && arr[i] <= target) {
i = i * 2;
}
// Call binary search for the found range
return binarySearch(arr, target, i / 2, std::min(i, n - 1));
}
private:
static int binarySearch(const std::vector<int>& arr, int target, int left, int right) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
public:
// Exponential Search for unbounded arrays
static int exponentialSearchUnbounded(std::function<int(int)> getElement, int target) {
int i = 1;
// Find the range where element might be present
while (getElement(i) != -1 && getElement(i) <= target) {
i = i * 2;
}
// Binary search in the found range
return binarySearchUnbounded(getElement, target, i / 2, i);
}
private:
static int binarySearchUnbounded(std::function<int(int)> getElement, int target, int left, int right) {
while (left <= right) {
int mid = left + (right - left) / 2;
int element = getElement(mid);
if (element == -1) {
right = mid - 1;
} else if (element == target) {
return mid;
} else if (element < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
};JAVA Implementation
// Exponential Search Implementation in Java
import java.util.function.Function;
public class ExponentialSearch {
public static int exponentialSearch(int[] arr, int target) {
int n = arr.length;
if (n == 0) return -1;
// If array has only one element
if (n == 1) {
return arr[0] == target ? 0 : -1;
}
// Find range for binary search
int i = 1;
while (i < n && arr[i] <= target) {
i = i * 2;
}
// Call binary search for the found range
return binarySearch(arr, target, i / 2, Math.min(i, n - 1));
}
private static int binarySearch(int[] arr, int target, int left, int right) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
// Exponential Search for unbounded arrays
public static int exponentialSearchUnbounded(Function<Integer, Integer> getElement, int target) {
int i = 1;
// Find the range where element might be present
while (getElement.apply(i) != null && getElement.apply(i) <= target) {
i = i * 2;
}
// Binary search in the found range
return binarySearchUnbounded(getElement, target, i / 2, i);
}
private static int binarySearchUnbounded(Function<Integer, Integer> getElement, int target, int left, int right) {
while (left <= right) {
int mid = left + (right - left) / 2;
Integer element = getElement.apply(mid);
if (element == null) {
right = mid - 1;
} else if (element == target) {
return mid;
} else if (element < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}JAVASCRIPT Implementation
// Exponential Search Implementation in JavaScript
function exponentialSearch(arr, target) {
const n = arr.length;
if (n === 0) return -1;
// If array has only one element
if (n === 1) {
return arr[0] === target ? 0 : -1;
}
// Find range for binary search
let i = 1;
while (i < n && arr[i] <= target) {
i = i * 2;
}
// Call binary search for the found range
return binarySearch(arr, target, Math.floor(i / 2), Math.min(i, n - 1));
}
function binarySearch(arr, target, left, right) {
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
// Exponential Search for unbounded arrays
function exponentialSearchUnbounded(getElement, target) {
let i = 1;
// Find the range where element might be present
while (getElement(i) !== null && getElement(i) <= target) {
i = i * 2;
}
// Binary search in the found range
return binarySearchUnbounded(getElement, target, Math.floor(i / 2), i);
}
function binarySearchUnbounded(getElement, target, left, right) {
while (left <= right) {
const mid = Math.floor((left + right) / 2);
const element = getElement(mid);
if (element === null) {
right = mid - 1;
} else if (element === target) {
return mid;
} else if (element < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}PYTHON Implementation
# Exponential Search Implementation in Python
def exponential_search(arr, target):
n = len(arr)
if n == 0:
return -1
# If array has only one element
if n == 1:
return 0 if arr[0] == target else -1
# Find range for binary search
i = 1
while i < n and arr[i] <= target:
i = i * 2
# Call binary search for the found range
return binary_search(arr, target, i // 2, min(i, n - 1))
def binary_search(arr, target, left, right):
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# Exponential Search for unbounded arrays
def exponential_search_unbounded(get_element, target):
i = 1
# Find the range where element might be present
while get_element(i) is not None and get_element(i) <= target:
i = i * 2
# Binary search in the found range
return binary_search_unbounded(get_element, target, i // 2, i)
def binary_search_unbounded(get_element, target, left, right):
while left <= right:
mid = (left + right) // 2
element = get_element(mid)
if element is None:
right = mid - 1
elif element == target:
return mid
elif element < target:
left = mid + 1
else:
right = mid - 1
return -1