Определите договорённости до написания кода
Входом служат список чисел и искомое значение. Результат должен однозначно показывать позицию первого совпадения либо отсутствие значения. Уточните, с нуля или с единицы считается позиция. Отдельно решите, что означает пустой список. Если числа могут повторяться, это не ошибка входа: алгоритм обязан соблюдать требование о первом совпадении. Такие договорённости называют контрактом задачи. Они помогают отличить дефект программы от ситуации, которую автор просто не описал. Проверяющий должен получить одинаковое понимание результата, не заглядывая в устройство решения.
Просмотрите элементы последовательно
Простой способ состоит в просмотре списка слева направо. Сравнивайте очередной элемент с искомым и возвращайте его позицию при совпадении. Если просмотр завершился, сообщайте об отсутствии. После каждой неудачной проверки известно, что среди уже просмотренных элементов совпадения нет. Это утверждение сохраняется на каждом шаге и объясняет корректность решения. Если нужное число оказалось первым, достаточно одного сравнения. Если его нет, придётся проверить весь список. Количество действий в худшем случае растёт примерно пропорционально числу элементов.
Используйте упорядоченность осмысленно
В отсортированном списке возможен двоичный поиск. Сравнение со средним элементом позволяет исключить примерно половину оставшегося диапазона. Если искомое число меньше среднего, оно может находиться только в левой части, и наоборот. Однако повторяющиеся значения усложняют требование найти первую позицию: обнаружив совпадение, нужно продолжить уточнение левой границы. Без предварительной сортировки этот способ не работает. Сама сортировка тоже требует работы и меняет расположение элементов. Поэтому ускорять единственный поиск сортировкой бывает невыгодно, особенно когда нужна позиция в исходном списке.
Проверяйте свойства, а не один пример
Набор тестов должен включать найденное значение в начале, середине и конце, отсутствующее значение, пустой список и повторения. Сначала вычислите ожидаемые ответы вручную, затем запускайте решение. Проверка только удобного случая может скрыть неверную границу цикла или ошибку в нумерации. Полезно также сравнивать два независимых решения на маленьких данных. Быстрое выполнение не доказывает правильность. Сначала установите, что результат соответствует контракту, и лишь затем оценивайте число сравнений и дополнительную память. Для коротких списков ясность простого решения часто важнее небольшого выигрыша времени.
Попробуйте на практике
Опишите и вручную выполните алгоритм поиска первой позиции, используя нумерацию с нуля.
- Возьмите список 8, 3, 8, 5. Запишите ожидаемые результаты поиска чисел 8, 5 и 7, а также поиска в пустом списке.
- Запишите последовательность действий обычными словами: начальное положение, проверка, переход к следующему элементу и завершение.
- Для каждого примера составьте короткий след выполнения: проверенная позиция, значение и принятое решение.
- Добавьте в начало списка число 8 и проверьте, что поиск по-прежнему возвращает первую позицию, а не последнее совпадение.
Как проверить результат. Ответы для исходного списка: 0 для числа 8, 3 для числа 5 и явное отсутствие для числа 7. Пустой список завершается без обращения к несуществующему элементу.
Частые вопросы
Обязательно ли сразу писать программу?
Нет. Точное описание и ручное выполнение на нескольких входах часто обнаруживают ошибки раньше кода. Затем эти же примеры становятся тестами программы.
Почему более сложный алгоритм не всегда лучше?
Он может требовать дополнительных условий, подготовки данных и более трудной проверки. Выбор зависит от размера входа, частоты поиска и того, какие свойства результата нужны.
Самостоятельный разбор темы. Содержание конкретной обучающей программы здесь не представлено.