Exponential Search Algorithm in C++

The exponential search is a strong algorithm for already sorted arrays. Its efficiency comes from a strategic combination of exponential growth and binary search techniques. The algorithm starts by shooting the array with exponentially increasing indices until it has a probable home of that target value. The first stage is like making a wide net over all array's elements.

This part of the algorithm doubles the index exponentially until it either go beyond the array's limit or find a value greater than or equal to the target. Due to its vast coverage capability, this doubling nature allows the algorithm to handle arrays of unknown or unbounded sizes. Once a suitable range is identified, the algorithm proceeds to the next phase: binary search within this more and more narrowed range.

Binary search, known for its high efficiency in dealing with sorted arrays, hits the exact location of a target value within a given range. The essence of the binary search is that it is applied exactly to the range determined during exponential growth. The algorithm balances the advantages of the exponential and binary search methods to swiftly zero in on the target value.

Exponential search has much better characteristics than linear or binary search algorithms, especially in the case of big datasets or when the size of the array is unknown (unbounded). The algorithm can approximate the possible ranges of its target value within a reasonable range and search binary if necessary. To wrap it up, the exponential search epitomizes the philosophy of efficient reduction of search areas using intelligent exploration followed by a fast and specific discovery of the wanted target value within a sorted array.

Approach 1: Recursive Exponential Search

The Recursive Exponential Search utilizes a recursive approach of traversing between the exponential indices in the sorted array. This iterative process helps quickly locate the range within which the target value may be found. When this range is determined, the algorithm proceeds to binary search within this narrowed interval to get to the exact target's position. With recursion, it cleverly and neatly traverses multiple array segments, yielding a clean and easy implementation. This approach combines the advantages of exponential growth and binary search; thus, it makes this method a strong solution to the problem of locating target values in the sorted arrays.

Program:

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 primarily depends on two factors:

Finding the Bound: If the number of operations required to double the bound exceeds the array size or the target value, the algorithm performance degrades, increasing the bound faster than necessary. These moves could be performed in O(log n) runtime, where 'n' represents the array's length.

Binary Search: After the initial range is specified, a binary search is done to find the exact position. Binary search gets a big O time complexity of log n, where the range size is n.

Overall Time Complexity:

Considering the worst-case scenario, where the target value is located at the end of the array or absent. The overall time complexity in such a case is the same, that is, O(log n), which means n is the size of the array.

Space Complexity:

A feature that determines the space complexity of the Recursive Exponential Search algorithm is the difference between the recursion depth amount and the number of steps the search is to go through.

The space consumed is a constant amount of additional needed for upholding parameters and local variables in every recursive call.

In the Recursive Exponential Search algorithm, the memory complexity is O(log n) as the height of the recursion stack is a maximum.

Approach 2: Iterative Exponential Search

The Exponential Search algorithm employs an iterative technique to explore exponentially increasing index values in a sorted array. It looks for the range where the target value could be by doubling the index until the value at that index becomes greater or equal to the target. Binary search is then applied repeatedly to narrow down this range into smaller and smaller intervals until the right value is found. This method requires no recursion and is suited for situations where recursion overhead should be excluded to make the implementation efficient but exponential at the same time.

Program:

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 primarily depends on two factors:

Finding the Bound: On the extreme example, the sequence of the iteration's doubles like 16, 32, 64, ...and so on, and continues till it becomes greater than the array size or approaches the target. This task needs an O (log n) time operation in which the n is the size of the array.

Binary Search: The selected range becomes the territory used for a binary search. The O(log n) complexity of binary search where 'n' is the size of the range.

Overall Time Complexity:

The worst case comes when the target is at the end position or is not there, and in such a condition, the time complexity would be O(log n), where n is the size of the array.

Space Complexity:

The additional memory space required in the Iterative Exponential Search algorithm is O(1), which means a constant space is used. This space, which is always earlier, is a worker of storing variables and parameters in functions.

The operations do not allocate or free the memory chunks, so they do not have recursion; therefore, the space complexity stays constant, whatever the size of the input array.