searches.interpolation_search

This is pure Python implementation of interpolation search algorithm

Functions

interpolation_search(→ int | None)	Searches for an item in a sorted collection by interpolation search algorithm.
interpolation_search_by_recursion(→ int | None)	Pure implementation of interpolation search algorithm in Python by recursion

Module Contents

searches.interpolation_search.interpolation_search(sorted_collection: list[int], item: int) → int | None

Searches for an item in a sorted collection by interpolation search algorithm.

Args:

sorted_collection: sorted list of integers item: item value to search

Returns:

int: The index of the found item, or None if the item is not found.

Examples: >>> interpolation_search([1, 2, 3, 4, 5], 2) 1 >>> interpolation_search([1, 2, 3, 4, 5], 4) 3 >>> interpolation_search([1, 2, 3, 4, 5], 6) is None True >>> interpolation_search([], 1) is None True >>> interpolation_search([100], 100) 0 >>> interpolation_search([1, 2, 3, 4, 5], 0) is None True >>> interpolation_search([1, 2, 3, 4, 5], 7) is None True >>> interpolation_search([1, 2, 3, 4, 5], 2) 1 >>> interpolation_search([1, 2, 3, 4, 5], 0) is None True >>> interpolation_search([1, 2, 3, 4, 5], 7) is None True >>> interpolation_search([1, 2, 3, 4, 5], 2) 1 >>> interpolation_search([5, 5, 5, 5, 5], 3) is None True

searches.interpolation_search.interpolation_search_by_recursion(sorted_collection: list[int], item: int, left: int = 0, right: int | None = None) → int | None

Pure implementation of interpolation search algorithm in Python by recursion Be careful collection must be ascending sorted, otherwise result will be unpredictable First recursion should be started with left=0 and right=(len(sorted_collection)-1)

Args:

sorted_collection: some sorted collection with comparable items item: item value to search left: left index in collection right: right index in collection

Returns:

index of item in collection or None if item is not present

Examples: >>> interpolation_search_by_recursion([0, 5, 7, 10, 15], 0) 0 >>> interpolation_search_by_recursion([0, 5, 7, 10, 15], 15) 4 >>> interpolation_search_by_recursion([0, 5, 7, 10, 15], 5) 1 >>> interpolation_search_by_recursion([0, 5, 7, 10, 15], 100) is None True >>> interpolation_search_by_recursion([5, 5, 5, 5, 5], 3) is None True