AntInLoop

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