searches.exponential_search

Pure Python implementation of exponential search algorithm

For more information, see the Wikipedia page: https://en.wikipedia.org/wiki/Exponential_search

For doctests run the following command: python3 -m doctest -v exponential_search.py

For manual testing run: python3 exponential_search.py

Attributes

user_input

Functions

binary_search_by_recursion(→ int)	Pure implementation of binary search algorithm in Python using recursion
exponential_search(→ int)	Pure implementation of an exponential search algorithm in Python.

Module Contents

searches.exponential_search.binary_search_by_recursion(sorted_collection: list[int], item: int, left: int = 0, right: int = -1) → int

Pure implementation of binary search algorithm in Python using recursion

Be careful: the collection must be ascending sorted otherwise, the result will be unpredictable.

Parameters:

• sorted_collection – some ascending sorted collection with comparable items

• item – item value to search

• left – starting index for the search

• right – ending index for the search

Returns:

index of the found item or -1 if the item is not found

Examples: >>> binary_search_by_recursion([0, 5, 7, 10, 15], 0, 0, 4) 0 >>> binary_search_by_recursion([0, 5, 7, 10, 15], 15, 0, 4) 4 >>> binary_search_by_recursion([0, 5, 7, 10, 15], 5, 0, 4) 1 >>> binary_search_by_recursion([0, 5, 7, 10, 15], 6, 0, 4) -1

searches.exponential_search.exponential_search(sorted_collection: list[int], item: int) → int

Pure implementation of an exponential search algorithm in Python. For more information, refer to: https://en.wikipedia.org/wiki/Exponential_search

Be careful: the collection must be ascending sorted, otherwise the result will be unpredictable.

Parameters:

• sorted_collection – some ascending sorted collection with comparable items

• item – item value to search

Returns:

index of the found item or -1 if the item is not found

The time complexity of this algorithm is O(log i) where i is the index of the item.

Examples: >>> exponential_search([0, 5, 7, 10, 15], 0) 0 >>> exponential_search([0, 5, 7, 10, 15], 15) 4 >>> exponential_search([0, 5, 7, 10, 15], 5) 1 >>> exponential_search([0, 5, 7, 10, 15], 6) -1

searches.exponential_search.user_input