Exponential Search is an algorithm designed for sorted datasets that combines the benefits of Binary Search and Jump Search. It finds the range where the target element might be located using exponentially increasing jumps (1, 2, 4, 8, …), then performs Binary Search within that range.
How Exponential Search Works?
- Start at the Beginning: Begin with the first element of the array.
- Exponential Jumps: Double the search range until the value at the current index is greater than or equal to the key, or the array boundary is exceeded.
- Binary Search: Perform a Binary Search in the identified range to locate the key.
- Return Result: If the key is found, return its index; otherwise, return
-1.
Exponential Search Java Program Examples
In this article, we’ll explore Exponential Search with two Java programs: a basic example for numeric arrays and an advanced implementation for searching within custom object lists.
1. Basic Program Example
This basic program performs Exponential Search on a numeric array to efficiently locate a given key, leveraging the combination of exponential jumps and Binary Search.
package com.javacodepoint.search;
public class BasicExponentialSearch {
public static int exponentialSearch(int[] array, int key) {
int n = array.length;
// If the key is at the first position
if (array[0] == key) {
return 0;
}
// Find the range for Binary Search
int i = 1;
while (i < n && array[i] <= key) {
i *= 2;
}
// Perform Binary Search in the found range
return binarySearch(array, i / 2, Math.min(i, n - 1), key);
}
private static int binarySearch(int[] array, int low, int high, int key) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (array[mid] == key) {
return mid;
}
if (array[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] numbers = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
int key = 70;
int result = exponentialSearch(numbers, key);
if (result != -1) {
System.out.println("Element found at index: " + result);
} else {
System.out.println("Element not found.");
}
}
}
OUTPUT:
Element found at index: 6
2. Advanced Program Example
This advanced program applies Exponential Search to a list of Employee objects. It searches for an employee based on their id, showcasing the algorithm’s versatility in handling complex data structures.
package com.javacodepoint.search;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
class Employee {
private int id;
private String name;
public Employee(int id, String name) {
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
@Override
public String toString() {
return "Employee{id=" + id + ", name='" + name + "'}";
}
}
public class AdvancedExponentialSearch {
public static int exponentialSearch(List<Employee> employees, int key) {
int n = employees.size();
// If the key is at the first position
if (employees.get(0).getId() == key) {
return 0;
}
// Find the range for Binary Search
int i = 1;
while (i < n && employees.get(i).getId() <= key) {
i *= 2;
}
// Perform Binary Search in the found range
return binarySearch(employees, i / 2, Math.min(i, n - 1), key);
}
private static int binarySearch(List<Employee> employees, int low, int high, int key) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (employees.get(mid).getId() == key) {
return mid;
}
if (employees.get(mid).getId() < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
public static void main(String[] args) {
List<Employee> employees = new ArrayList<>();
employees.add(new Employee(101, "Alice"));
employees.add(new Employee(102, "Bob"));
employees.add(new Employee(103, "Charlie"));
employees.add(new Employee(104, "David"));
int key = 103;
// Sort employees by ID
employees.sort(Comparator.comparingInt(Employee::getId));
int result = exponentialSearch(employees, key);
if (result != -1) {
System.out.println("Employee found: " + employees.get(result));
} else {
System.out.println("Employee not found.");
}
}
}
OUTPUT:
Employee found: Employee{id=103, name=’Charlie’}
Time Complexity (Exponential Search)
- Best Case: O(logn) (for uniformly distributed, sorted data).
- Worst Case: O(logn), as it involves both the exponential jump and Binary Search.
You can explore other search algorithms like Linear Search, Binary Search, Interpolation Search, Fibonacci Search, Ternary Search, and Jump Search.