searches.binary_search ====================== .. py:module:: searches.binary_search .. autoapi-nested-parse:: Pure Python implementations of binary search algorithms For doctests run the following command: python3 -m doctest -v binary_search.py For manual testing run: python3 binary_search.py Attributes ---------- .. autoapisummary:: searches.binary_search.name searches.binary_search.searches Functions --------- .. autoapisummary:: searches.binary_search.binary_search searches.binary_search.binary_search_by_recursion searches.binary_search.binary_search_std_lib searches.binary_search.bisect_left searches.binary_search.bisect_right searches.binary_search.exponential_search searches.binary_search.insort_left searches.binary_search.insort_right Module Contents --------------- .. py:function:: binary_search(sorted_collection: list[int], item: int) -> int Pure implementation of a binary search algorithm in Python Be careful collection must be ascending sorted otherwise, the result will be unpredictable :param sorted_collection: some ascending sorted collection with comparable items :param item: item value to search :return: index of the found item or -1 if the item is not found Examples: >>> binary_search([0, 5, 7, 10, 15], 0) 0 >>> binary_search([0, 5, 7, 10, 15], 15) 4 >>> binary_search([0, 5, 7, 10, 15], 5) 1 >>> binary_search([0, 5, 7, 10, 15], 6) -1 .. py:function:: binary_search_by_recursion(sorted_collection: list[int], item: int, left: int = 0, right: int = -1) -> int Pure implementation of a binary search algorithm in Python by recursion Be careful collection must be ascending sorted otherwise, the result will be unpredictable First recursion should be started with left=0 and right=(len(sorted_collection)-1) :param sorted_collection: some ascending sorted collection with comparable items :param item: item value to search :return: 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 .. py:function:: binary_search_std_lib(sorted_collection: list[int], item: int) -> int Pure implementation of a binary search algorithm in Python using stdlib Be careful collection must be ascending sorted otherwise, the result will be unpredictable :param sorted_collection: some ascending sorted collection with comparable items :param item: item value to search :return: index of the found item or -1 if the item is not found Examples: >>> binary_search_std_lib([0, 5, 7, 10, 15], 0) 0 >>> binary_search_std_lib([0, 5, 7, 10, 15], 15) 4 >>> binary_search_std_lib([0, 5, 7, 10, 15], 5) 1 >>> binary_search_std_lib([0, 5, 7, 10, 15], 6) -1 .. py:function:: bisect_left(sorted_collection: list[int], item: int, lo: int = 0, hi: int = -1) -> int Locates the first element in a sorted array that is larger or equal to a given value. It has the same interface as https://docs.python.org/3/library/bisect.html#bisect.bisect_left . :param sorted_collection: some ascending sorted collection with comparable items :param item: item to bisect :param lo: lowest index to consider (as in sorted_collection[lo:hi]) :param hi: past the highest index to consider (as in sorted_collection[lo:hi]) :return: index i such that all values in sorted_collection[lo:i] are < item and all values in sorted_collection[i:hi] are >= item. Examples: >>> bisect_left([0, 5, 7, 10, 15], 0) 0 >>> bisect_left([0, 5, 7, 10, 15], 6) 2 >>> bisect_left([0, 5, 7, 10, 15], 20) 5 >>> bisect_left([0, 5, 7, 10, 15], 15, 1, 3) 3 >>> bisect_left([0, 5, 7, 10, 15], 6, 2) 2 .. py:function:: bisect_right(sorted_collection: list[int], item: int, lo: int = 0, hi: int = -1) -> int Locates the first element in a sorted array that is larger than a given value. It has the same interface as https://docs.python.org/3/library/bisect.html#bisect.bisect_right . :param sorted_collection: some ascending sorted collection with comparable items :param item: item to bisect :param lo: lowest index to consider (as in sorted_collection[lo:hi]) :param hi: past the highest index to consider (as in sorted_collection[lo:hi]) :return: index i such that all values in sorted_collection[lo:i] are <= item and all values in sorted_collection[i:hi] are > item. Examples: >>> bisect_right([0, 5, 7, 10, 15], 0) 1 >>> bisect_right([0, 5, 7, 10, 15], 15) 5 >>> bisect_right([0, 5, 7, 10, 15], 6) 2 >>> bisect_right([0, 5, 7, 10, 15], 15, 1, 3) 3 >>> bisect_right([0, 5, 7, 10, 15], 6, 2) 2 .. py:function:: exponential_search(sorted_collection: list[int], item: int) -> int Pure implementation of an exponential search algorithm in Python Resources used: https://en.wikipedia.org/wiki/Exponential_search Be careful collection must be ascending sorted otherwise, result will be unpredictable :param sorted_collection: some ascending sorted collection with comparable items :param item: item value to search :return: index of the found item or -1 if the item is not found the order of this algorithm is O(lg I) where I is index position of item if exist 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 .. py:function:: insort_left(sorted_collection: list[int], item: int, lo: int = 0, hi: int = -1) -> None Inserts a given value into a sorted array before other values with the same value. It has the same interface as https://docs.python.org/3/library/bisect.html#bisect.insort_left . :param sorted_collection: some ascending sorted collection with comparable items :param item: item to insert :param lo: lowest index to consider (as in sorted_collection[lo:hi]) :param hi: past the highest index to consider (as in sorted_collection[lo:hi]) Examples: >>> sorted_collection = [0, 5, 7, 10, 15] >>> insort_left(sorted_collection, 6) >>> sorted_collection [0, 5, 6, 7, 10, 15] >>> sorted_collection = [(0, 0), (5, 5), (7, 7), (10, 10), (15, 15)] >>> item = (5, 5) >>> insort_left(sorted_collection, item) >>> sorted_collection [(0, 0), (5, 5), (5, 5), (7, 7), (10, 10), (15, 15)] >>> item is sorted_collection[1] True >>> item is sorted_collection[2] False >>> sorted_collection = [0, 5, 7, 10, 15] >>> insort_left(sorted_collection, 20) >>> sorted_collection [0, 5, 7, 10, 15, 20] >>> sorted_collection = [0, 5, 7, 10, 15] >>> insort_left(sorted_collection, 15, 1, 3) >>> sorted_collection [0, 5, 7, 15, 10, 15] .. py:function:: insort_right(sorted_collection: list[int], item: int, lo: int = 0, hi: int = -1) -> None Inserts a given value into a sorted array after other values with the same value. It has the same interface as https://docs.python.org/3/library/bisect.html#bisect.insort_right . :param sorted_collection: some ascending sorted collection with comparable items :param item: item to insert :param lo: lowest index to consider (as in sorted_collection[lo:hi]) :param hi: past the highest index to consider (as in sorted_collection[lo:hi]) Examples: >>> sorted_collection = [0, 5, 7, 10, 15] >>> insort_right(sorted_collection, 6) >>> sorted_collection [0, 5, 6, 7, 10, 15] >>> sorted_collection = [(0, 0), (5, 5), (7, 7), (10, 10), (15, 15)] >>> item = (5, 5) >>> insort_right(sorted_collection, item) >>> sorted_collection [(0, 0), (5, 5), (5, 5), (7, 7), (10, 10), (15, 15)] >>> item is sorted_collection[1] False >>> item is sorted_collection[2] True >>> sorted_collection = [0, 5, 7, 10, 15] >>> insort_right(sorted_collection, 20) >>> sorted_collection [0, 5, 7, 10, 15, 20] >>> sorted_collection = [0, 5, 7, 10, 15] >>> insort_right(sorted_collection, 15, 1, 3) >>> sorted_collection [0, 5, 7, 15, 10, 15] .. py:data:: name :value: ' binary_search_std_lib' .. py:data:: searches