[Feature]: Want to add interpolation search algorithm in search folder

Feature Name

Interpolation search algorithm

Feature Description

Interpolation Search is an efficient search algorithm, especially suited for cases where the data is uniformly distributed. It can outperform Binary Search in such situations due to its better positioning strategy, which estimates the position of the search value rather than just using the midpoint (as in Binary Search).

Motivation

Adding Interpolation Search as a feature in Algo (or any algorithm toolkit) would be highly beneficial for users who work with large, sorted datasets that have a uniform or close-to-uniform distribution. This algorithm provides a valuable alternative to Binary Search by offering a faster average case performance of 𝑂(log(log 𝑛)) for certain data distributions, making it ideal for scenarios where search efficiency is paramount, such as in database indexing, large analytics platforms, and certain types of search engines.

Implementation Suggestions (Optional)

Function Signature:
- Use public static int interpolationSearch(int[] array, int target); to keep consistency with Binary Search.
Validation Checks:
- Ensure the input array is sorted and roughly uniformly distributed to maximize efficiency.

Feature Type

New Algorithm

Does this feature require additional resources?

[ ] Additional Documentation
[ ] Third-Party Libraries
[ ] UI/UX Design
[X] Other

References (Optional)

https://www.geeksforgeeks.org/interpolation-search/

ajay-dhangar / algo