The exponential search algorithm is a powerful technique tailored for arrays that are already in sorted order. Its effectiveness lies in the clever amalgamation of exponential progression and binary search strategies. Initially, the algorithm probes the array by incrementing indices exponentially until it homes in on a potential location for the target value. This initial phase can be likened to casting a broad net over all the elements in the array.
This segment of the algorithm multiplies the index by a factor of two repeatedly until it surpasses the boundary of the array or locates a value that is equal to or greater than the target. Because of its extensive coverage capacity, this exponential growth property enables the algorithm to manage arrays of unspecified or infinite sizes. After pinpointing an appropriate interval, the algorithm advances to the subsequent step: conducting a binary search within this increasingly restricted range.
Binary search, recognized for its exceptional performance when working with sorted arrays, precisely identifies the position of a specified value within a defined range. The fundamental concept behind binary search involves narrowing down the search to the range established through exponential expansion. By combining the strengths of exponential and binary search approaches, this algorithm efficiently converges on the desired target value.
Exponential search offers superior qualities compared to linear or binary search methods, particularly when dealing with large datasets or arrays of unknown size (unbounded). This algorithm is capable of estimating potential ranges for the target value effectively and resorting to binary search if required. In essence, exponential search embodies the concept of smartly narrowing down search areas through strategic exploration, leading to a swift and precise identification of the desired target value within a sorted array.
Approach 1: Recursive Exponential Search
The Recursive Exponential Search employs a recursive strategy to navigate through the exponential indexes within the ordered array. This iterative method efficiently identifies the potential range where the desired value might exist. Once this interval is identified, the algorithm then conducts a binary search within this reduced scope to pinpoint the precise position of the target. Through recursion, it adeptly explores various segments of the array, offering a streamlined and straightforward implementation. By merging the benefits of exponential expansion and binary search, this technique emerges as a robust resolution for pinpointing target values in sorted arrays.
Program:
#include <iostream>
#include <vector>
//Function to perform binary search within a sorted array
int binarySearch(std::vector<int>& arr, int left, int right, int target) {
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; // Return -1 if target is not found
}
//Function to perform hybrid exponential and interpolation search
int exponentialInterpolationSearch(std::vector<int>& arr, int target) {
int n = arr.size();
if (n == 0)
return -1; // Return -1 if the array is empty
// Find the range for binary search by exponentially increasing the index
int bound = 1;
while (bound < n && arr[bound] < target)
bound *= 2;
// Applying interpolation to approximate position within the range
int left = bound / 2;
int right = std::min(bound, n - 1);
while (left <= right) {
// Linear interpolation formula to estimate position
int pos = left + ((double)(right - left) / (arr[right] - arr[left])) * (target - arr[left]);
if (pos < 0 || pos >= n)
break;
if (arr[pos] == target)
return pos;
else if (arr[pos] < target)
left = pos + 1;
else
right = pos - 1;
}
// Call binary search within the identified range
return binarySearch(arr, left, right, target);
}
int main() {
std::vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}; // Sample sorted array
int target = 13; // Target value to search
int result = exponentialInterpolationSearch(arr, target);
if (result != -1)
std::cout << "Element found at index " << result << std::endl;
else
std::cout << "Element not found in the array." << std::endl;
return 0;
}
Output:
Element found at index 6
Explanation:
- binarySearch Function: After sorting, this operation is performed on the array, and the location is found on the element. The state of the Function is that it gives the related array (arr) and left and right values (left and right) closely and the target value (target). The algorithm is performed cyclically and divides the space of search into halves so that if the target element is situated, it is found or if all the space is depleted. If successfully carried out, it prints the index of the found value; otherwise, it returns -1.
- exponentialSearchRecursive Function: The probability here is the state of recurrence in which the exponential search happens. It is exposed (arr), parameter (target) that are bound, and bounds (bound) limits the sizes of its parameter list. This, in turn, splits the interval into two different parts and eventually narrows down the result range where the target can be located. The final algorithm yields the index of where the target stands if it is discovered at the time range; aside from this, the algorithm gives -1. The result limit value of output becomes either outside the range or lower than the initial value; it keeps returning -1.
- exponentialSearch Function: This wrapper function carries the exp interpolation search, which in the array arr represents the source of data and the target as its parameters. It first verifies if the array is empty; otherwise, it returns -1. It searches for the value range of binary searching by doubling the index until the value of that index is greater than or equal to the target. Next, it invokes the binarySearch Function through the range specified, and eventually, it forwards the given results accordingly.
- Main Function: It is the initial step in the program. The method proceeds with initializing the sorted array sample (arr) and the target value (target) it should search for. The algorithm begins with the exponential search and finally verifies the result by the second half of the array. If the target is found, it prints its index signature; in the alternative, it prints a message saying the element is not found. The computer stops working after the program has been run.
Complexity Analysis:
Time Complexity:
Exponential Search (Recursive):
The time complexity of the exponential search is predominantly influenced by two key factors:
Determining the Boundary: When the number of operations needed to double the boundary surpasses either the size of the array or the target value, it leads to a deterioration in the algorithm's efficiency by escalating the boundary unnecessarily quickly. These operations can be executed in O(log n) time complexity, with 'n' denoting the length of the array.
Binary Search: Following the selection of the initial range, a binary search operation is performed to pinpoint the precise location. The binary search algorithm achieves a time complexity of O(log n), corresponding to the size of the range being n.
Overall Time Complexity:
In a scenario where the target value is situated at the array's end or is not present, the time complexity remains unchanged at O(log n), where n represents the array's size.
Space Complexity:
A factor that influences the space efficiency of the Recursive Exponential Search algorithm is the variance between the depth of recursion and the total steps required for the search process.
The amount of memory used remains consistent, requiring a fixed space to store parameters and local variables during each recursive invocation.
In the Recursive Exponential Search technique, the memory usage is O(log n) since the recursion stack's height is at most that value.
Approach 2: Iterative Exponential Search
The Exponential Search algorithm utilizes an iterative approach to investigate exponentially growing index positions within a sorted array. It seeks the potential range of the target value by doubling the index until the value at that position is greater than or equal to the target value. Subsequently, Binary search is used iteratively to reduce this range into increasingly smaller intervals until the correct value is identified. This technique eliminates the need for recursion and is ideal for scenarios where avoiding recursion overhead is crucial for efficient implementation, while also maintaining an exponential behavior.
Program:
#include <iostream>
#include <vector>
//Function to perform binary search within a sorted array
int binarySearch(std::vector<int>& arr, int left, int right, int target) {
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; // Return -1 if target is not found
}
//Function to perform an iterative exponential search
int exponentialSearch(std::vector<int>& arr, int target) {
int n = arr.size();
if (n == 0)
return -1; // Return -1 if the array is empty
// Find the range for binary search by doubling the index
int bound = 1;
while (bound < n && arr[bound] < target)
bound *= 2;
// Call binary search within the identified range
return binarySearch(arr, bound / 2, std::min(bound, n - 1), target);
}
int main() {
std::vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}; // Sample sorted array
int target = 13; // Target value to search
int result = exponentialSearch(arr, target);
if (result != -1)
std::cout << "Element found at index " << result << std::endl;
else
std::cout << "Element not found in the array." << std::endl;
return 0;
}
Output:
Element found at index 6
Explanation:
- binarySearch Function: This method has a specific task performing a binary search within an already sorted array. The array's elements are the left and right indices and the target value. It operationally divide the search space in half each time in an iterative way until the target value is found or the search space is exhausted. When the target is found, this Function returns the index; otherwise, -1.
- exponentialSearch Function: This method is responsible for the iterative element of exponential search. It has the arrays and targets as parameters. The method begins by examining whether an array is empty; if it is, it returns -1. Next, it determines the range using the doubling strategy of the index until the index value is equal to or larger than the target. Finishing the exercise, it calls the binarySearch function in the identified section of the array and returns the result.
- Main Function: These are the first steps in this program. It invokes an array arr of a random sorted order and a number target to look for. It searches for the array's target value by coding the exponentialSearch Function. Otherwise, the array is printed with an info message stating the element does not exist. The program stops on execution after it finishes.
Complexity Analysis:
Time Complexity:
Exponential Search (Iterative):
The time complexity of the iterative exponential search mainly relies on two key factors:
Determining the Limit: In a more extreme scenario, the sequence of doubling the iterations such as 16, 32, 64, etc., persists until it surpasses the array size or nears the target value. This particular task requires an operation that runs in O(log n) time complexity, where n represents the array's size.
Binary Search: The chosen interval is designated as the domain for conducting a binary search algorithm. The time complexity of O(log n) associated with binary search is determined by the size 'n' of the range being searched.
Overall Time Complexity:
The most challenging scenario arises when the desired element is either located at the final position or is not present at all. In such a scenario, the time complexity would be O(log n), where n represents the array's size.
Space Complexity:
The extra memory space needed in the Iterative Exponential Search method is O(1), indicating a consistent usage of space. This allocated space, positioned at the beginning, serves as a container for holding variables and function parameters.
The functions do not reserve or release memory blocks, hence they do not involve recursion; thus, the spatial complexity remains unchanged, regardless of the array's size.
