Repository: keon/algorithms
Pull request #686 (2020-08-13 12:35:34)

Adding the interpolation search algorithm
I saw that interpolation search hasn't been implemented yet so I thought I would add the algorithm.

ericklarac: @reinhold-b could you add some tests for the algorithm?. Also, include your algorithm on the readme file. You can take the following PR as a guide https://github.com/keon/algorithms/pull/631/files
reinhold-b: For some reason my code editor was formatting the readme. Should be fine now...

Patch:
diff --git a/README.md b/README.md
index 79c1d08..c1b3692 100644
--- a/README.md
+++ b/README.md
@@ -258,6 +258,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [search_rotate](algorithms/search/search_rotate.py)
     - [jump_search](algorithms/search/jump_search.py)
     - [next_greatest_letter](algorithms/search/next_greatest_letter.py)
+    - [interpolation_search](algorithms/search/interpolation_search.py)
 - [set](algorithms/set)
     - [randomized_set](algorithms/set/randomized_set.py)
     - [set_covering](algorithms/set/set_covering.py)
diff --git a/algorithms/search/__init__.py b/algorithms/search/__init__.py
index ac5220b..2586605 100644
--- a/algorithms/search/__init__.py
+++ b/algorithms/search/__init__.py
@@ -9,3 +9,4 @@ from .find_min_rotate import *
 from .search_rotate import *
 from .jump_search import *
 from .next_greatest_letter import *
+from .interpolation_search import *
diff --git a/algorithms/search/interpolation_search.py b/algorithms/search/interpolation_search.py
new file mode 100644
index 0000000..0759180
--- /dev/null
+++ b/algorithms/search/interpolation_search.py
@@ -0,0 +1,53 @@
+""" 
+Python implementation of the Interpolation Search algorithm.
+Given a sorted array in increasing order, interpolation search calculates
+the starting point of its search according to the search key.
+
+FORMULA: start_pos = low + [ (x - arr[low])*(high - low) / (arr[high] - arr[low]) ]
+
+Doc: https://en.wikipedia.org/wiki/Interpolation_search
+
+Time Complexity: O(log2(log2 n)) for average cases, O(n) for the worst case.
+The algorithm performs best with uniformly distributed arrays.
+"""
+
+from typing import List
+
+
+def interpolation_search(array: List[int], search_key: int) -> int:
+    """
+    :param array: The array to be searched.
+    :param search_key: The key to be searched in the array.
+
+    :returns: Index of search_key in array if found, else -1.
+
+    Example
+
+    >>> interpolation_search([1, 10, 12, 15, 20, 41, 55], 20)
+    4
+    >>> interpolation_search([5, 10, 12, 14, 17, 20, 21], 55)
+    -1
+
+    """
+
+    # highest and lowest index in array
+    high = len(array) - 1
+    low = 0
+
+    while low <= high and search_key in range(low, array[high] + 1):
+        # calculate the search position
+        pos = low + int(((search_key - array[low]) *
+                         (high - low) / (array[high] - array[low])))
+
+        # if array[pos] equals the search_key then return pos as the index
+        if search_key == array[pos]:
+            return pos
+        # if the search_key is greater than array[pos] restart the search with the
+        # subarray greater than array[pos]
+        elif search_key > array[pos]:
+            low = pos + 1
+        # in this case start the search with the subarray smaller than current array[pos]
+        elif search_key < array[pos]:
+            high = pos - 1
+
+    return -1


Test patch:
diff --git a/tests/test_search.py b/tests/test_search.py
index 60d8919..3f6c23f 100644
--- a/tests/test_search.py
+++ b/tests/test_search.py
@@ -9,11 +9,13 @@ from algorithms.search import (
     find_min_rotate, find_min_rotate_recur,
     search_rotate, search_rotate_recur,
     jump_search,
-    next_greatest_letter, next_greatest_letter_v1, next_greatest_letter_v2
+    next_greatest_letter, next_greatest_letter_v1, next_greatest_letter_v2,
+    interpolation_search
 )
 
 import unittest
 
+
 class TestSuite(unittest.TestCase):
 
     def test_first_occurrence(self):
@@ -56,7 +58,7 @@ class TestSuite(unittest.TestCase):
         self.assertEqual(-1, linear_search(array, -1))
 
     def test_search_insert(self):
-        array = [1,3,5,6]
+        array = [1, 3, 5, 6]
         self.assertEqual(2, search_insert(array, 5))
         self.assertEqual(1, search_insert(array, 2))
         self.assertEqual(4, search_insert(array, 7))
@@ -122,6 +124,16 @@ class TestSuite(unittest.TestCase):
         self.assertEqual("c", next_greatest_letter_v1(letters, target))
         self.assertEqual("c", next_greatest_letter_v2(letters, target))
 
+    def test_interpolation_search(self):
+        array = [0, 3, 5, 5, 9, 12, 12, 15, 16, 19, 20]
+        self.assertEqual(1, interpolation_search(array, 3))
+        self.assertEqual(2, interpolation_search(array, 5))
+        self.assertEqual(6, interpolation_search(array, 12))
+        self.assertEqual(-1, interpolation_search(array, 22))
+        self.assertEqual(-1, interpolation_search(array, -10))
+        self.assertEqual(10, interpolation_search(array, 20))
+
+
 if __name__ == '__main__':
 
     unittest.main()