Exponential Search & Unbounded Binary Search

Lecture 61 :- Exponential Search & Unbounded Binary Search

Exponential Search and Unbounded Binary Search are both searching algorithms used to find a specific target element in a sorted array, but they have different approaches and use cases. Let's explore each algorithm:

1. Exponential Search:
   • Exponential Search is an improved version of Binary Search for unbounded or infinite-sized arrays.
   • It works by finding an appropriate range (exponential interval) in which the target element may exist.
   • Initially, the range starts with the first element and keeps doubling until the range's upper bound becomes larger than the target.
   • Once the range is found, Binary Search is performed within that range to locate the target element.
   • This algorithm is particularly useful when the size of the array is not known, or it's prohibitively large to perform Binary Search directly.

Here's the C++ implementation of Exponential Search:

cppCopy code

#include <iostream> #include <vector> 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; } int exponentialSearch(std::vector<int>& arr, int target) {    int n = arr.size();    if (arr[0] == target) {        return 0;    }    int i = 1;    while (i < n && arr[i] <= target) {        i *= 2;    }    return binarySearch(arr, i / 2, std::min(i, n - 1), target); } int main() {    std::vector<int> arr = {2, 4, 6, 8, 10, 12, 14, 16};    int target = 8;    int index = exponentialSearch(arr, target);    if (index != -1) {        std::cout << "Element found at index " << index << std::endl;    } else {        std::cout << "Element not found in the array." << std::endl;    }    return 0; }

1. Unbounded Binary Search:
   • Unbounded Binary Search is used to find the position of an element in an infinite-sized sorted array or an array with unknown size.
   • The algorithm starts by finding a range in which the target may exist. It keeps doubling the range until it finds an upper bound larger than the target.
   • After finding the range, it performs Binary Search within that range to locate the target element.
   • This algorithm is useful when dealing with data structures like linked lists, which can be traversed but do not allow direct access to elements.

Both Exponential Search and Unbounded Binary Search are useful in specific scenarios when dealing with large or unknown-sized datasets. They provide efficient ways to locate elements without having to traverse the entire dataset linearly.