WikiGalaxy
Exponential Search
Introduction to Exponential Search
Exponential Search is an algorithm that is particularly useful for searching in sorted arrays. It combines the power of binary search with exponential growth to quickly find the range where the element might be present, then performs a binary search within that range.
How Exponential Search Works
The algorithm begins with a bound of 1 and doubles it until the bound exceeds the length of the array or the element at that position is greater than the target value. Once the suitable range is found, a binary search is performed in that range.
public class ExponentialSearch {
public static int exponentialSearch(int arr[], int n, int x) {
if (arr[0] == x) return 0;
int i = 1;
while (i < n && arr[i] <= x) i = i * 2;
return binarySearch(arr, i / 2, Math.min(i, n), x);
}
public static int binarySearch(int arr[], int low, int high, int x) {
if (high >= low) {
int mid = low + (high - low) / 2;
if (arr[mid] == x) return mid;
if (arr[mid] > x) return binarySearch(arr, low, mid - 1, x);
return binarySearch(arr, mid + 1, high, x);
}
return -1;
}
public static void main(String args[]) {
int arr[] = {2, 3, 4, 10, 40};
int x = 10;
int result = exponentialSearch(arr, arr.length, x);
System.out.println((result < 0) ? "Element not found" : "Element found at index " + result);
}
}
Example 1: Basic Exponential Search
In this example, we search for the number 10 in a sorted array {2, 3, 4, 10, 40}. The exponential search quickly identifies the range and the binary search confirms its position at index 3.
Example 2: Element Not Found
If we search for an element not present in the array, such as 5, the exponential search will determine the range and the binary search will return -1, indicating the element is not found.
Console Output:
Element found at index 3
Exponential Search in Large Arrays
Handling Large Datasets
Exponential Search is especially effective in large datasets where the element is closer to the beginning, as it can quickly identify the range and perform a binary search within it.
public class LargeArraySearch {
public static void main(String args[]) {
int arr[] = new int[1000];
for (int i = 0; i < 1000; i++) arr[i] = i * 2;
int x = 198;
int result = ExponentialSearch.exponentialSearch(arr, arr.length, x);
System.out.println((result < 0) ? "Element not found" : "Element found at index " + result);
}
}
Example 3: Searching in Large Arrays
This example demonstrates searching for the number 198 in an array of 1000 elements. The exponential search efficiently narrows down the range, allowing the binary search to quickly find the element at index 99.
Console Output:
Element found at index 99
Exponential Search with Duplicate Elements
Handling Duplicates
When dealing with duplicate elements, exponential search will find the first occurrence in the range identified. If multiple occurrences exist, further logic might be needed to identify all instances.
public class DuplicateElementSearch {
public static void main(String args[]) {
int arr[] = {1, 2, 4, 4, 4, 5, 6, 7};
int x = 4;
int result = ExponentialSearch.exponentialSearch(arr, arr.length, x);
System.out.println((result < 0) ? "Element not found" : "First occurrence at index " + result);
}
}
Example 4: Searching with Duplicates
In this example, we search for the number 4 in an array containing duplicates. The exponential search identifies the range and the binary search finds the first occurrence at index 2.
Console Output:
First occurrence at index 2
Exponential Search in Sparse Arrays
Sparse Array Considerations
Sparse arrays, which contain many empty or null elements, can benefit from exponential search by quickly skipping over large sections of empty data to find the relevant range.
public class SparseArraySearch {
public static void main(String args[]) {
String arr[] = {"", "", "", "apple", "", "", "banana", "", "cherry"};
String x = "banana";
int result = ExponentialSearch.exponentialSearch(arr, arr.length, x);
System.out.println((result < 0) ? "Element not found" : "Element found at index " + result);
}
}
Example 5: Searching in Sparse Arrays
This example searches for the word "banana" in a sparse array. Exponential search efficiently identifies the range, allowing the binary search to locate the element at index 6.
Console Output:
Element found at index 6
