На этом шаге мы наметим план дальнейшего изложения.
Начиная с этого шага, мы будем рассматривать алгоритмы, решающие классическую задачу поиска позиции i элемента x в списке a = [a0, a1, ..., an-1]. Другими словами, для заданных a и x найти индекс i, для которого ai = x. Если элемент x не единственный в списке, то метод решения задачи может вернуть любой индекс, указывающий на позицию x в списке.
Для списка длины n метод решения задачи должен вернуть целочисленный индекс в пределах от 0 до n - 1, если элемент x найден в списке. Напротив, если список не содержит x, алгоритм должен вернуть некоторое значение за пределами этого интервала. Некоторые реализации Python просто возвращают логическое значение False. Однако такой возможности нет во многих других языках (C, Java, Паскаль и т. д.), где методы могут возвращать только значения одного типа данных. Поскольку индексы - это, безусловно, целые числа, в этих языках результат должен быть также целым числом. Таким образом, ради совместимости с другими языками программирования мы будем использовать целочисленное значение -1 в случае, когда элемент не найден в списке.
На следующем шаге мы рассмотрим линейный поиск.
