GrokkingAlgorithms/09 binary search recursion.py at main · AlexTkDev/GrokkingAlgorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
# Бинарный поиск, используя рекурсию. [O(log n)]

# Создаем функцию "binary_search", которая принимает 4 входных параметра:
# список "search_list", переменные "low" и "high", которые хранят границы области поиска в списке "search_list",
# и число для поиска "element".
# Эта функция возвращает индекс элемента, который является числом для поиска "number".
def binary_search(search_list, low, high, element):
    # Создаем локальную переменную "upper_bound_error_list", которую мы используем для проверки указанных
    # границ области поиска:
    # 1. не превышает ли указанная верхняя граница действительную верхнюю границу списка "search_list";
    # 2. не является ли указанная нижняя граница меньше действительной нижней границы списка "search_list".
    upper_bound_error_list = []
    # В блоке try, используя цикл for, пытаемся перебрать все элементы списка "search_list"
    # и поместить их в список "upper_bound_error_list", при помощи метода "append".
    # Функция "range()" возвращает последовательность чисел, за исключением последнего число.
    try:
        for i in range(low, high+1):
            upper_bound_error_list.append(search_list[i])
    # В блоке except пытаемся перехватить ошибку "IndexError", в случае если
    # мы пытаемся поместить в список "upper_bound_error_list" элемент,
    # который имеет индекс больший максимального индекса в списке "search_list"
    # или который имеет индекс меньший минимального индекса в списке "search_list".
    # Если мы успешно перехватываем ошибку "IndexError", то выводится сообщение об ошибке и
    # программа продолжает свою работу.
    # Ключевое слово "return" выходит из функции и возвращает какое-либо значение.
    # Функция "print()" выводит некую указанную информацию на экран или на какое-либо другое устройство вывода.
    except IndexError:
        return print("The specified upper bound is greater than the actual upper bound of the list "
                     "or the specified lower bound is less than the actual lower bound of the list \n"
                     "----------")
    # Если указанная нижняя граница меньше или равна указанной верхней границе,
    # а также эта нижняя граница больше или равна 0,
    # то находим индекс среднего элемента списка "search_list".
    # Переменная "mid" хранит этот индекс среднего элемента.
    # Значение переменной "mid" округляется в меньшую сторону.
    if high >= low >= 0:
        mid = low + (high - low) // 2
        # Создаем базовый случай.
        # Базовый случай в рекурсивной функции - это часть функции, в которой описывается
        # условие прекращения работы функции в целях предотвращения зацикливания.
        # Если значение среднего элемента списка "search_list" равно числу, которое мы ищем,
        # или же если список "search_list" содержит 1 элемент и этот элемент равен числу, которое мы ищем,
        # то функция "binary_search" возвращает индекс этого среднего элемента.
        if search_list[mid] == element:
            return print("The element we are looking for is at index %d \n"
                         "----------" % mid)
        # Создаем рекурсивный случай.
        # Рекурсивный случай в рекурсивной функции - это часть функции, в которой функция вызывает сама себя
        # в целях выполнения какой-либо задачи.
        # Если значение среднего элемента списка "search_list" больше числа, которого мы ищем,
        # то рекурсивно вызывается новая копия функции "binary_search", в которой
        # верхняя граница области поиска становится равной на одну позицию меньше,
        # чем индекс этого среднего элемента.
        elif search_list[mid] > element:
            return binary_search(search_list, low, mid - 1, element)
        # Иначе если значение среднего элемента списка "search_list" меньше числа, которого мы ищем,
        # то рекурсивно вызывается новая копия функции "binary_search", в которой
        # нижняя граница области поиска становится равной на одну позицию больше,
        # чем индекс этого среднего элемента.
        else:
            return binary_search(search_list, mid + 1, high, element)
    # Если число для поиска отсутствует в списке "search_list" (условие "high >= low" не является верным,
    # этот факт означает, что область поиска пуста),
    # или если указанная нижняя граница меньше действительной нижней границы списка "search_list",
    # или если указанная верхняя граница превышает действительную верхнюю границу списка "search_list",
    # то функция "binary_search" выводит соответствующее сообщение об ошибке.
    else:
        return print("The element we are looking for is not in the list or "
                     "the specified upper bound is greater than the actual upper bound of the list "
                     "or the specified lower bound is less than the actual lower bound of the list \n"
                     "----------")
    # В этой функции "binary_search" не учтено условие, когда указанные границы области поиска образуют список, который
    # входит в список "search_list", но является меньше списка "search_list".
    # Например, если "search_list" = [1, 2, 3, 4], "low" = 1, "high" = 2, "element" = 4,
    # то эти указанные границы образуют список [2, 3] и программа все равно попытается найти число "element".

# Создаем список чисел "my_list".
my_list = [0, 2, 6, 7, 7, 9]


# Создаем переменную "x", хранящую число, которое находится в списке "my_list".
x = 6


# Создаем переменную "y", хранящую число, которое не находится в списке "my_list".
y = 4


# Попытаемся вызвать функцию "binary_search" c разными наборами входных параметрами.
# Все параметры указаны верно.
# Функция "len()" возвращает количество элементов в списке.
binary_search(my_list, 0, len(my_list) - 1, x)


# Нижняя граница указана неверно.
binary_search(my_list, -1, len(my_list) - 1, x)


# Нижняя граница указана неверно.
binary_search(my_list, -7, len(my_list) - 1, x)


# Верхняя граница указана неверно.
binary_search(my_list, 0, 6, x)


# Верхняя граница указана неверно.
binary_search(my_list, 0, -1, x)


# Верхняя граница указана неверно.
binary_search(my_list, 0, -8, x)


# Указанная нижняя граница больше указанной верхней границы.
binary_search(my_list, 3, 2, x)


# Число, которое нужно найти, указано неверно.
binary_search(my_list, 0, len(my_list) - 1, y)


# Указанные границы образуют список,
# который входит в список "search_list", но является меньше списка "search_list".
binary_search(my_list, 1, 4, x)