searches.binary_search

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

name
searches

Functions

binary_search(→ int)	Pure implementation of a binary search algorithm in Python
binary_search_by_recursion(→ int)	Pure implementation of a binary search algorithm in Python by recursion
binary_search_std_lib(→ int)	Pure implementation of a binary search algorithm in Python using stdlib
bisect_left(→ int)	Locates the first element in a sorted array that is larger or equal to a given
bisect_right(→ int)	Locates the first element in a sorted array that is larger than a given value.
exponential_search(→ int)	Pure implementation of an exponential search algorithm in Python
insort_left(→ None)	Inserts a given value into a sorted array before other values with the same value.
insort_right(→ None)	Inserts a given value into a sorted array after other values with the same value.

Module Contents

searches.binary_search.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

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

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

searches.binary_search.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)

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

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.binary_search.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

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

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

searches.binary_search.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 .

Parameters:

• sorted_collection – some ascending sorted collection with comparable items

• item – item to bisect

• lo – lowest index to consider (as in sorted_collection[lo:hi])

• hi – past the highest index to consider (as in sorted_collection[lo:hi])

Returns:

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

searches.binary_search.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 .

Parameters:

• sorted_collection – some ascending sorted collection with comparable items

• item – item to bisect

• lo – lowest index to consider (as in sorted_collection[lo:hi])

• hi – past the highest index to consider (as in sorted_collection[lo:hi])

Returns:

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

searches.binary_search.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

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 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

searches.binary_search.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 .

Parameters:

• sorted_collection – some ascending sorted collection with comparable items

• item – item to insert

• lo – lowest index to consider (as in sorted_collection[lo:hi])

• 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]

searches.binary_search.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 .

Parameters:

• sorted_collection – some ascending sorted collection with comparable items

• item – item to insert

• lo – lowest index to consider (as in sorted_collection[lo:hi])

• 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]

searches.binary_search.name = '     binary_search_std_lib'

searches.binary_search.searches