Урок 6-7. Поиск элементов с заданными свойствами

Любая программа обрабатывает данные. Часто эти данные представлены в виде массивов — структур, хранящих набор элементов одного типа. Одной из самых частых задач при работе с массивами является поиск элемента, удовлетворяющего определённому условию.

Примеры из реальной жизни:

• Поиск номера телефона абонента в списке контактов.

• Поиск книги по названию в библиотечной базе данных.

• Поиск оценок ученика в электронном журнале.

Сегодня мы рассмотрим два основных алгоритма поиска: линейный и двоичный.

Важно! Перед началом любой работы за компьютером помните о правилах техники безопасности. Самое главное: не трогайте разъёмы и провода, работайте спокойно, не торопясь, и обо всех нестандартных ситуациях (запах гари, необычный звук) немедленно сообщайте учителю.

2. Теоретический материал

2.1. Линейный поиск (последовательный поиск)

Суть алгоритма: Последовательно, шаг за шагом, просматриваются все элементы массива от первого до последнего. Каждый элемент проверяется на соответствие заданному условию. Поиск прекращается, когда элемент найден или когда просмотрен весь массив.

📊 Схема алгоритма:
Начало -> Установить счётчик i = 1 -> Сравнить i-ый элемент с искомым -> (Если совпадает) -> Вывести результат -> Конец
-> (Если не совпадает) -> Увеличить i на 1 -> (Если i > N) -> Вывести "Не найдено" -> Конец

Где применяется:

• Поиск в неупорядоченных массивах (где элементы идут в случайном порядке).

• Поиск по сложному условию (например, найти первого ученика, у которого рост больше 170 см, а оценка по математике "5").

• Когда массив мал по размеру.

Преимущества и недостатки:

Преимущества

Простота реализации.

Низкая скорость на больших массивах.

Универсальность (любые условия для поиска).

Недостатки:

Работает с неупорядоченными данными.

В худшем случае требует просмотра всех элементов.

Пример кода на Pascal: Поиск первого вхождения числа X в массив.

pascal

program LinearSearch;

var

  arr: array[1..10] of integer = (5, 2, 9, 1, 5, 6, 3, 8, 4, 7);

  i, X: integer;

  found: boolean;

begin

  write('Введите число для поиска: ');

  readln(X);

  found := false; // Флаг, означающий, что элемент пока не найден

  i := 1;

  while (i <= 10) and (not found) do

  begin

    if arr[i] = X then

    begin

      found := true;

      writeln('Число ', X, ' найдено на позиции ', i);

    end;

    i := i + 1;

  end;

  if not found then

    writeln('Число ', X, ' не найдено в массиве.');

end.

2.2. Двоичный (бинарный) поиск

Суть алгоритма: Быстрый алгоритм поиска в отсортированном массиве (например, упорядоченном по возрастанию). На каждом шаге интервал поиска сокращается вдвое.

📊 Схема алгоритма:

1. Найти средний элемент отсортированного массива.

2. Сравнить его с искомым значением.

3. Если они равны — поиск завершён.

4. Если искомое значение меньше среднего элемента — продолжить поиск в левой половине массива.

5. Если искомое значение больше среднего элемента — продолжить поиск в правой половине массива.

6. Шаги повторяются до тех пор, пока элемент не будет найден или пока интервал поиска не станет пустым.

Где применяется:

• Только в отсортированных массивах.

• Поиск в больших объёмах данных (базы данных, телефонные справочники, словари).

Преимущества и недостатки:

Преимущества

Очень высокая скорость (даже на больших массивах).

Эффективность: количество шагов ~ log2(N).

Недостатки

Требует предварительной сортировки массива.

Работает только с упорядоченными данными.

Сложнее в реализации по сравнению с линейным.

Пример кода на Pascal: Поиск числа X в отсортированном массиве.

pascal

program BinarySearch;

var

  arr: array[1..10] of integer = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10); // Обязательно отсортированный!

  first, last, mid, X: integer;

  found: boolean;

begin

  write('Введите число для поиска: ');

  readln(X);

  first := 1;     // Левая граница поиска

  last := 10;     // Правая граница поиска

  found := false; // Элемент не найден

  while (first <= last) and (not found) do

  begin

    mid := (first + last) div 2; // Находим середину интервала

    if arr[mid] = X then

      found := true

    else

      if arr[mid] > X then

        last := mid - 1 // Ищем в левой половине

      else

        first := mid + 1; // Ищем в правой половине

  end;

  if found then

    writeln('Число ', X, ' найдено на позиции ', mid)

  else

    writeln('Число ', X, ' не найдено в массиве.');

end.

Вывод: Выбор алгоритма зависит от задачи. Если массив невелик или не отсортирован — используйте линейный поиск. Если массив большой и отсортирован — двоичный поиск намного эффективнее.

Видео урок по данному уроку от учителя информатики Трашкова Олега Леонидовича