Difference between exponential search and binary search and Fibonacci search

1. Binary SearchApproach:Binary Search works by repeatedly dividing the search interval in half. If the target value is less than the middle element of the interval, the search continues on the left half; other wise, it continues on the right half.Time Complexity: O(log n)Requirements: The array must be sorted.Best Use Case: Ideal for searching in static sorted arrays where the size of the array is known.

2. Exponential SearchApproach:Exponential Search is designed for unbounded or infinite arrays (or arrays where the size is unknown). It starts by checking the first element, then the elements at increasing exponential indices (1, 2, 4, 8, ...). Once it finds a range where the target might exist, it applies Binary Search within that range.Time Complexity: O(log n)Requirements: The array must be sorted. Best suited for unbounded or very large sorted arrays where the size isn't known in advance.Best Use Case: Searching in large or infinite-sized arrays, or when the position of the element is closer to the beginning.

3. Fibonacci SearchApproach:Fibonacci Search divides the array into sections based on Fibonacci numbers, using them to determine the size of the search interval. The algorithm exploits the property that a Fibonacci sequence divides an array into two sections where the sizes of the sections are themselves Fibonacci numbers. This allows efficient narrowing of the search range.Time Complexity: O(log n)Requirements: The array must be sorted.Best Use Case: Works similarly to Binary Search but can be more efficient on certain hardware due to the arithmetic operations involved in computing Fibonacci numbers, which may reduce the number of comparisons.

Key DifferencesStarting Point:

Binary Search:- Begins by dividing the entire array in half.

Exponential Search: Begins with a small sub-array and gradually expands the range exponentially.

Fibonacci Search: Begins by partitioning the array using Fibonacci numbers, which may differ from the mid-point split of Binary Search.

Efficiency:

Binary Search: Efficient for static sorted arrays.

Exponential Search: More efficient when dealing with large or unbounded arrays .

Fibonacci Search: Can be more efficient on certain systems, particularly where comparison costs are high.

Array Size:

Binary Search: Assumes a known, fixed array size.

Exponential Search: Suitable for unknown or unbounded arrays.

Fibonacci Search: Typically used when comparisons are expensive or in systems where Fibonacci sequence-based partitioning is more efficient.

In summary, while Binary Search is a general-purpose search algorithm for sorted arrays, Exponential Search and Fibonacci Search offer specialized approaches for scenarios involving unknown array sizes or environments where specific computational efficiencies are needed.