TheAlgorithms-Python

1
from __future__ import annotations
2

3

4
def find_min_iterative(nums: list[int | float]) -> int | float:
5
    """
6
    Find Minimum Number in a List
7
    :param nums: contains elements
8
    :return: min number in list
9

10
    >>> for nums in ([3, 2, 1], [-3, -2, -1], [3, -3, 0], [3.0, 3.1, 2.9]):
11
    ...     find_min_iterative(nums) == min(nums)
12
    True
13
    True
14
    True
15
    True
16
    >>> find_min_iterative([0, 1, 2, 3, 4, 5, -3, 24, -56])
17
    -56
18
    >>> find_min_iterative([])
19
    Traceback (most recent call last):
20
        ...
21
    ValueError: find_min_iterative() arg is an empty sequence
22
    """
23
    if len(nums) == 0:
24
        raise ValueError("find_min_iterative() arg is an empty sequence")
25
    min_num = nums[0]
26
    for num in nums:
27
        min_num = min(min_num, num)
28
    return min_num
29

30

31
# Divide and Conquer algorithm
32
def find_min_recursive(nums: list[int | float], left: int, right: int) -> int | float:
33
    """
34
    find min value in list
35
    :param nums: contains elements
36
    :param left: index of first element
37
    :param right: index of last element
38
    :return: min in nums
39

40
    >>> for nums in ([3, 2, 1], [-3, -2, -1], [3, -3, 0], [3.0, 3.1, 2.9]):
41
    ...     find_min_recursive(nums, 0, len(nums) - 1) == min(nums)
42
    True
43
    True
44
    True
45
    True
46
    >>> nums = [1, 3, 5, 7, 9, 2, 4, 6, 8, 10]
47
    >>> find_min_recursive(nums, 0, len(nums) - 1) == min(nums)
48
    True
49
    >>> find_min_recursive([], 0, 0)
50
    Traceback (most recent call last):
51
        ...
52
    ValueError: find_min_recursive() arg is an empty sequence
53
    >>> find_min_recursive(nums, 0, len(nums)) == min(nums)
54
    Traceback (most recent call last):
55
        ...
56
    IndexError: list index out of range
57
    >>> find_min_recursive(nums, -len(nums), -1) == min(nums)
58
    True
59
    >>> find_min_recursive(nums, -len(nums) - 1, -1) == min(nums)
60
    Traceback (most recent call last):
61
        ...
62
    IndexError: list index out of range
63
    """
64
    if len(nums) == 0:
65
        raise ValueError("find_min_recursive() arg is an empty sequence")
66
    if (
67
        left >= len(nums)
68
        or left < -len(nums)
69
        or right >= len(nums)
70
        or right < -len(nums)
71
    ):
72
        raise IndexError("list index out of range")
73
    if left == right:
74
        return nums[left]
75
    mid = (left + right) >> 1  # the middle
76
    left_min = find_min_recursive(nums, left, mid)  # find min in range[left, mid]
77
    right_min = find_min_recursive(
78
        nums, mid + 1, right
79
    )  # find min in range[mid + 1, right]
80

81
    return left_min if left_min <= right_min else right_min
82

83

84
if __name__ == "__main__":
85
    import doctest
86

87
    doctest.testmod(verbose=True)
88