C++ Program to Implement Exponential Search
By Coder Scratchpad on in C/C++
Searching efficiently in a large, sorted array is a common task for programmers. While binary search is a popular method, exponential search is another powerful technique designed to quickly find the range where the target element might exist. Exponential search works by repeatedly doubling the index until the target is smaller than the element at that index, and then it performs a binary search within that range.
This search algorithm is particularly useful when you don’t know the size of the array or when you need a quick way to locate the probable range before applying a more precise search. Beginners will find exponential search helpful because it combines two concepts—exponential growth and binary search—demonstrating how combining strategies can improve efficiency in programming.
Table of Contents
Toggle- Program 1: Exponential Search Using Loops
- Program 2: Exponential Search with User Input
- Program 3: Recursive Exponential Search
- Frequently Asked Questions (FAQ)
- Conclusion
Program 1: Exponential Search Using Loops
This program demonstrates the iterative approach to exponential search. It first finds the range using exponential growth and then performs a binary search in that range.
#include <iostream>
using namespace std;
int binarySearch(int arr[], int left, int right, int key) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
int exponentialSearch(int arr[], int n, int key) {
if (arr[0] == key)
return 0;
int i = 1;
while (i < n && arr[i] <= key)
i = i * 2;
return binarySearch(arr, i / 2, min(i, n - 1), key);
}
int main() {
int arr[] {1, 3, 5, 7, 9, 11, 13, 15};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 11;
int result = exponentialSearch(arr, n, key);
if (result != -1)
cout << "Element " << key << " found at index " << result << endl;
else
cout << "Element " << key << " not found in the array." << endl;
return 0;
}
#include <iostream>
using namespace std;
int binarySearch(int arr[], int left, int right, int key) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
int exponentialSearch(int arr[], int n, int key) {
if (arr[0] == key)
return 0;
int i = 1;
while (i < n && arr[i] <= key)
i = i * 2;
return binarySearch(arr, i / 2, min(i, n - 1), key);
}
int main() {
int arr[] {1, 3, 5, 7, 9, 11, 13, 15};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 11;
int result = exponentialSearch(arr, n, key);
if (result != -1)
cout << "Element " << key << " found at index " << result << endl;
else
cout << "Element " << key << " not found in the array." << endl;
return 0;
}
In this program, the array is first scanned exponentially, doubling the index each time until the key is smaller than the current element. After finding the probable range, a binary search is applied to locate the element precisely. Beginners can see how combining two search strategies makes the algorithm efficient for large arrays.
Program 2: Exponential Search with User Input
This version allows the user to enter the element they want to search, demonstrating exponential search in an interactive scenario.
#include <iostream>
using namespace std;
int binarySearch(int arr[], int left, int right, int key) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
int exponentialSearchInteractive(int arr[], int n, int key) {
if (arr[0] == key)
return 0;
int i = 1;
while (i < n && arr[i] <= key)
i = i * 2;
return binarySearch(arr, i / 2, min(i, n - 1), key);
}
int main() {
int arr[] {2, 4, 6, 8, 10, 12, 14, 16};
int n = sizeof(arr) / sizeof(arr[0]);
int key;
cout << "Enter the element to search: ";
cin >> key;
int result = exponentialSearchInteractive(arr, n, key);
if (result != -1)
cout << "Element " << key << " found at index " << result << endl;
else
cout << "Element " << key << " not found in the array." << endl;
return 0;
}
#include <iostream>
using namespace std;
int binarySearch(int arr[], int left, int right, int key) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
int exponentialSearchInteractive(int arr[], int n, int key) {
if (arr[0] == key)
return 0;
int i = 1;
while (i < n && arr[i] <= key)
i = i * 2;
return binarySearch(arr, i / 2, min(i, n - 1), key);
}
int main() {
int arr[] {2, 4, 6, 8, 10, 12, 14, 16};
int n = sizeof(arr) / sizeof(arr[0]);
int key;
cout << "Enter the element to search: ";
cin >> key;
int result = exponentialSearchInteractive(arr, n, key);
if (result != -1)
cout << "Element " << key << " found at index " << result << endl;
else
cout << "Element " << key << " not found in the array." << endl;
return 0;
}
This interactive program helps beginners experiment with different keys and see how the algorithm quickly identifies the range before using binary search. It reinforces the concept of exponential growth in search.
Program 3: Recursive Exponential Search
This program demonstrates a recursive approach, which combines recursion with binary search for cleaner and more elegant code.
#include <iostream>
using namespace std;
int binarySearchRecursive(int arr[], int left, int right, int key) {
if (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
return binarySearchRecursive(arr, mid + 1, right, key);
else
return binarySearchRecursive(arr, left, mid - 1, key);
}
return -1;
}
int exponentialSearchRecursive(int arr[], int n, int key) {
if (arr[0] == key)
return 0;
int i = 1;
while (i < n && arr[i] <= key)
i = i * 2;
return binarySearchRecursive(arr, i / 2, min(i, n - 1), key);
}
int main() {
int arr[] {1, 5, 9, 13, 17, 21, 25};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 17;
int result = exponentialSearchRecursive(arr, n, key);
if (result != -1)
cout << "Element " << key << " found at index " << result << endl;
else
cout << "Element " << key << " not found in the array." << endl;
return 0;
}
#include <iostream>
using namespace std;
int binarySearchRecursive(int arr[], int left, int right, int key) {
if (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
return binarySearchRecursive(arr, mid + 1, right, key);
else
return binarySearchRecursive(arr, left, mid - 1, key);
}
return -1;
}
int exponentialSearchRecursive(int arr[], int n, int key) {
if (arr[0] == key)
return 0;
int i = 1;
while (i < n && arr[i] <= key)
i = i * 2;
return binarySearchRecursive(arr, i / 2, min(i, n - 1), key);
}
int main() {
int arr[] {1, 5, 9, 13, 17, 21, 25};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 17;
int result = exponentialSearchRecursive(arr, n, key);
if (result != -1)
cout << "Element " << key << " found at index " << result << endl;
else
cout << "Element " << key << " not found in the array." << endl;
return 0;
}
The recursive version makes the code modular and readable, demonstrating how exponential search can be combined with recursion for a clean implementation. Beginners can learn how recursion works in real-world search problems.
Frequently Asked Questions (FAQ)
Here are some common questions about exponential search:
Q1: What is exponential search?
Exponential Search is an algorithm that quickly finds a range by doubling indices and then performs a binary search within that range.
Q2: When is exponential search useful?
It is useful for large, sorted arrays or when the size of the array is unknown.
Q3: Can it work on unsorted arrays?
No, the array must be sorted for exponential search to function correctly.
Q4: What is the time complexity of exponential search?
Exponential search has a time complexity of O(log n), making it efficient for large datasets.
Q5: How is exponential search different from binary search?
Exponential search first finds a probable range using exponential growth, while binary search directly splits the whole array. This makes exponential search faster when the element is near the beginning.
Conclusion
Exponential Search is a powerful and efficient searching algorithm for sorted arrays, especially when the size of the array is unknown or when elements are concentrated near the start. In this article, we explored iterative, interactive, and recursive implementations in C++, showing beginners how the algorithm identifies a range exponentially and then applies binary search for precise results.
Practicing exponential search helps beginners understand how combining strategies—exponential growth and binary search—can optimize search efficiency. By experimenting with different arrays and keys, learners can strengthen their understanding of search algorithms and build a solid foundation for more advanced programming concepts.