Алгоритмы поиска

АЛГОРИТМЫ ПОИСКА

Цель работы: Освоить и закрепить приемы работы с алгоритмами поиска числовых и строковых данных. Получить навыки применения алгоритмов поиска для практических задач.

Ключевые понятия, которые необходимо знать: линейный (последовательный) поиск, бинарный поиск, интерполяционный поиск, алгоритм Кнута-Мориса-Пратта, алгоритм Боуера-Мура-Хорспула, алгоритм Рабина-Карпа.

1 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Одно из наиболее часто встречающихся в программировании действий – поиск. С точки зрения программирования различают поиск среди числовых и строковых данных.

Для числовых данных наиболее употребительны такие алгоритмы, как:

- последовательный (линейный) поиск,

- бинарный поиск,

- интерполяционный поиск.

Для поиска текстовых данных (поиск подстроки в тексте) наиболее используемы следующие алгоритмы:

- линейный (последовательный) поиск подстроки,

- алгоритм Кнута-Мориса-Пратта,

- алгоритм Боуера-Мура-Хорспула,

- алгоритм Рабина-Карпа.

1.1 Поиск числовых данных

Рассмотрим методы поиска числовых данных для следующей задачи: дан массив mas[N] численных значений (ключей) размером N элементов; необходимо найти позицию заданного ключа K в массиве mas, в случае успешного поиска, или сообщить о том, что К не содержится в mas.

1.1.1 Последовательный (линейный) поиск. «Начать с начала и продолжать, пока не будет найден искомый ключ (значение); затем остановиться» – эта последовательная процедура представляет собой очевидный и самый простой путь поиска [1]. Он применяется, если нет никакой дополнительной информации о разыскиваемых данных.

Пример последовательного поиска приведен в программном примере 1.

/*== Программный пример 1 – Последовательный поиск ==*/

• int linSearch(int arr[], int requiredKey, int arrSize)
• {
•  for (int i = 0; i < arrSize; i++)
•  {
•  if (arr[i] == requiredKey)
•  return i;
•  }
•  return -1;
• }

Когда размер массива небольшой, последовательный поиск работает достаточно быстро. Последовательный поиск достаточно прост, но время его работы прямо пропорционально количеству данных, которые нужно просмотреть; удвоение количества элементов приведет к удвоению времени на поиск, если искомого элемента в массиве нет.

1.1.2 Бинарный поиск. Хорошо известно, что поиск можно сделать значительно более эффективным, если данные будут упорядочены. Один из простых методов поиска в упорядоченном массиве является бинарный поиск (поиск делением пополам), который заключается в следующем:

а) проверяем средний элемент массива с искомым;

б) если это значение больше, чем искомое, то ищем далее в первой части; в противном случае ищем во второй части;

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

Пример бинарного поиска приведен в программном примере 2.

/*== Программный пример 2 – Бинарный поиск ==*/

int BinarySearch(int mas[], int k, int masSize)

{ //k - искомое значение в массиве mas

  //результат – позиция значения k в массиве mas

  //  или -1, если k не содержится в массиве mas

  int L = 0;  //Нижняя граница рассматриваемого диапазо-на

  //Верхняя граница рассматриваемого диапазона

  int H = masSize - 1;

  int m;

  while (L <= H) //Пока рассматриваемый диапазон не будет пуст

  { m = (L + H) / 2;//Индекс среднего элемента