Interpolation search algorithm 
Tags: algorithms, beginners, computerscience, codenewbie
Published: 2021-06-19 19:23:46

## definition of interpolation search

> The Interpolation Search is an improvement over Binary Search for instances, where the values in a sorted array are uniformly distributed. Binary Search always goes to the middle element to check. On the other hand, interpolation search may go to different locations according to the value of the key being searched. For example, if the value of the key is closer to the last element, interpolation search is likely to start search toward the end side.
>- [*www.geeksforgeeks.org*](https://www.google.com/amp/s/www.geeksforgeeks.org/interpolation-search/amp/)

## Space complexity
The space complexity of interpolation search is O(1)

## Time complexity of interpolation search

| Best case | Average case  | Worst case |
|-----------|---------------|------------|
| O(1)      | O(log2(log2 n)) | O(n)       |

## Formula of interpolation search

the formula of interpolation search is:
`pos = low + ((x – A[low]) * (high – low) // (A[high] – A[low]))`
if you asked like me how we got this formula checkout this amazing [article](https://medium.com/@smellycode/demystifying-interpolation-formula-for-interpolation-search-211780c43269) by *Hitesh Kumar*

## Algorithm of interpolation search

1. calculating the pos using the formula above
2. if `array[pos] == wantedElement`: return pos
3. if `array[pos] > wantedElement` : `high = pos - 1`
4. if `array[pos] < wantedElement` : `low = pos + 1`
5. stay repeating until the `array[pos] == wantedElement` or the sub-array reduces to zero.

## Implementation of interpolation search using python
```python
def InterpolationSearchAlgorithm(wantedItem: int, sortedItems: list):
    """
        => Algorithm Name: Interpolation search
        => Algorithm Type: search algorithms
        => Time Complexity: 
            [best case]     => O(1)
            [average case]  => O(log2(log2 n))
            [worst case]    => O(n)
        => Space Complexity => O(1)
        => Algorithm
            [1] =>  calculating the pos using the formula above
            [2] =>  if `array[pos] == wantedElement`: return pos
            [3] =>  if `array[pos] > wantedElement` : `high = pos - 1`
            [4] =>  if `array[pos] < wantedElement` : `low = pos + 1`
            [5] =>  stay repeating until the `array[pos] == wantedElement` or the sub-array reduces to zero.
        => params
            (wantedItem) => int
            (sortedItems) => sorted list and equally distributed.
        => Returns 
            (index) if the wanted item exists in the sortedItems
            (False) if the wanted item doesn't exist 
    """
    low = 0 
    high = len(sortedItems) - 1
    while (high >= low and sortedItems[high] >= wantedItem and sortedItems[low] <= wantedItem):
        # formula of interpolation sort
        pos = low + ((high - low) // (sortedItems[high] - sortedItems[low]) *
                    (wantedItem - sortedItems[low]))
                    
        if sortedItems[pos] == wantedItem:
            # if it match return his index (pos)
            return pos
        elif sortedItems[pos] < wantedItem:
            # if A[pos] is smaller than wantedItem
            low = pos + 1
        else:
            # if A[pos] is larger than wantedItem
            high = pos - 1
    return False
```

## References and useful resources

+ [https://www.techiedelight.com/interpolation-search/](https://www.techiedelight.com/interpolation-search/)
+ [https://medium.com/@smellycode/demystifying-interpolation-formula-for-interpolation-search-211780c43269](https://medium.com/@smellycode/demystifying-interpolation-formula-for-interpolation-search-211780c43269)
+ [https://www.geeksforgeeks.org/interpolation-search/](https://www.geeksforgeeks.org/interpolation-search/)
+ [https://www.youtube.com/watch?v=-MPTAD4z0gY](https://www.youtube.com/watch?v=-MPTAD4z0gY)
+ 
 [https://en.wikipedia.org/wiki/Interpolation_search#:~:text=Interpolation%20search%20is%20an%20algorithm,by%20W.%20W.%20Peterson%20in%201957.](https://en.wikipedia.org/wiki/Interpolation_search#:~:text=Interpolation%20search%20is%20an%20algorithm,by%20W.%20W.%20Peterson%20in%201957.)

\#day_7
Have a great day!