BinarySearch#

class BinarySearch#

Bases: Algorithm[Iterable[Comparable], int, int]

__init__()#

Methods

`__init__`()
`get_worst_case_arguments`(input_size)	Generates a sorted range of integers from 1 to input_size and a searched for element (input_size + 1) which is not present in the array.
`increment_n_ops`([increment])	Convenience method to increment n_ops count of the given complexity object.
`reset_n_ops`()	Convenience method to reset n_ops count of the given complexity object.
`run_algorithm`(input_instance[, ...])	Run function of the binary search algorithm.

Attributes

`algorithm_family`	rtype: `AlgorithmFamily`
`algorithm_properties`	rtype: `AlgorithmProperties`
`average_case_time_complexity`	rtype: `str`
`best_case_description`	rtype: `str`
`best_case_time_complexity`	rtype: `str`
`is_deterministic`	rtype: `bool`
`n_ops`	rtype: `int`
`name`	rtype: `str`
`space_complexity`	rtype: `str`
`worst_case_description`	rtype: `str`
`worst_case_time_complexity`	rtype: `str`

property algorithm_family: AlgorithmFamily#

Return type:: AlgorithmFamily

property algorithm_properties: AlgorithmProperties#

Return type:: AlgorithmProperties

property average_case_time_complexity: str#

Return type:: str

property best_case_description: str#

Return type:: str

property best_case_time_complexity: str#

Return type:: str

get_worst_case_arguments(input_size)#

Generates a sorted range of integers from 1 to input_size and a searched for element (input_size + 1) which is not present in the array.

Parameters:: input_size (int) – Size of the range to generate.
Returns:: run_algorithm_kwargs – A dictionary with keyword arguments for the ̈́’input_instance’ and ‘element_to_search’ parameters of the run_algorithm method.
Return type:: dict[str, Any]

increment_n_ops(increment=1)#

Convenience method to increment n_ops count of the given complexity object.

Return type:: None

property is_deterministic: bool#

Return type:: bool

property n_ops: int#

Return type:: int

property name: str#

Return type:: str

reset_n_ops()#

Convenience method to reset n_ops count of the given complexity object.

Return type:: None

run_algorithm(input_instance, verbosity_level=0, element_to_search=None, *args, **kwargs)#

Run function of the binary search algorithm.

Parameters:

input_instance (Iterable[Comparable]) – Iterable input instance of comparable objects to run the search algorithm on. Has to be sorted, otherwise the algorithm will not work as expected.
verbosity_level (int (default 0)) – Select the amount of information to print throughout run of the algorithm. One of 0, 1, 2 with 0 referring to no printing, 1 leading to print results after and 2 meaning print bisected element after every step.
element_to_search (Optional[Comparable] (default None)) – Element to search for in the given input_instance. If None, the algorithm immediately successfully terminates.
args (Any) – Additional arguments passed to the running function.
kwargs (Any) – Additional keyword arguments passed to the running function.

Returns:

result – Returns boolean value representing whether the algorithm terminated successfully (True if element_to_search is None or the given element was found in the input_instance) and an index of the element if it was found, otherwise None.

Return type:

tuple[bool, Optional[int]]

property space_complexity: str#

Return type:: str

property worst_case_description: str#

Return type:: str

property worst_case_time_complexity: str#

Return type:: str