Модели и структуры данных

Алгоритмы, структуры данных и программирование

• Лекция № 11
• Алгоритмы поиска

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

• Одно из наиболее часто встречающихся в программировании действий это - поиск.
• Существует несколько основных вариантов поиска, и для них создано много различных алгоритмов.

Линейный поиск

• Линейный или последовательный поиск – один из самых простых алгоритмов поиска элемента в массиве.
• Алгоритм заключается в последовательном обходе всех элементов неупорядоченного массива, как правило слева направо, и сравнения их с ключевым значением.
• Если значения элемента и ключа совпадают, то поиск считается завершённым, и в зависимости от назначения, возвращает значение или индекс элемента.

Линейный поиск

• Линейный поиск применяется для нахождения:
• индекса заданного элемента массива;
• индексов минимального или максимального элемента;
• минимального или максимального значения в массиве;
• Рассмотрим методы расширения, которые реализуют выше перечисленные варианты. Для того, чтобы методы можно было применять к разным типам данных, будем использовать
• универсальные шаблоны(generics).

Линейный поиск

• Для начала создадим статический класс, в кото-рый будем помещать все рассмотренные методы. Добавим в класс метод для проверки(не имеет смысла работать с пустым массивом):

• public static class ArrayExt {
• private static void CheckArray (T[] a) {
• if (a == null) {
• throw new ArgumentNullException("Массив не может быть нулевым"); }
• if (a.Length == 0) {
• throw new ArgumentException("Длина массива должна быть больше нуля"); }
• }
• }