Введение в алгоритмы поиска в C++

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

Следовательно, нам нужны некоторые эффективные методы поиска или алгоритмы, которые помогут искать заданную часть информации за короткое время и предоставят ее пользователю, чтобы он мог приступить к другим задачам.

Методы поиска

Есть два основных метода поиска, которые в основном используются для поиска информации, это:

  • Линейный поиск
  • Бинарный поиск

В этой статье мы подробно рассмотрим оба этих метода поиска.

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

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

Рассмотрим следующий массив:

Пример массива

Выше показан массив из семи элементов. Если мы хотим найти ключ = 23, то начиная с 0-го элемента значение ключа будет сравниваться с каждым элементом. Как только ключевой элемент совпадет с элементом в массиве, будет возвращено это конкретное местоположение. В этом случае будет возвращено значение 3, так как ключ-значение соответствует значению в этом местоположении.

Читать также:  Типы данных С++

Ниже мы реализовали линейный поиск с использованием языков C++ и Java.

Скетч на С++:

Вывод данных:

Входной массив:
21 43 23 54 75 13 5 8 25 10
Введите ключ для поиска: 3
Не удалось найти данный ключ в массиве
Входной массив:
21 43 23 54 75 13 5 8 25 10
Введите ключ для поиска: 75
Ключ найден в позиции 5 в массиве

Скетч на Java:

Вывод данных:

Входной массив6
21 43 23 54 75 13 5 8 25 10
Клавиша ввода6
23
ключ найден в локации: 3

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

Бинарный поиск

Бинарный поиск — это метод, который использует метод «разделяй и властвуй» для поиска ключа. Он работает с отсортированным линейным списком элементов. Отсортированный список является основным требованием для работы бинарного поиска.

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

Читать также:  Математические функции С++: absolutevalue, sqrt, max, pow и другие

Например, возьмем следующий отсортированный массив из 10 элементов:

Отсортированный массив

Допустим, ключ = 21 нужно искать в массиве.

Вычислим среднее расположение массива.

Середина = 0+9/2 = 4

Например, возьмем следующий отсортированный массив из 10 элементов:

Следующий отсортированный массив

Ключ = 21

Сначала мы сравним значение ключа с элементом [mid]. Мы видим, что значение элемента в середине = 21.

Значение ключа

Таким образом, мы находим, что key = [mid], т.е. ключ = середина. Значит, ключ найден.

ключ = 25

Сначала мы сравниваем значение ключа со значением mid. Итак (21 < 25), мы будем искать ключ непосредственно в верхней половине массива:

Поиск ключа

Теперь снова найдем середину верхней половины массива.

mid = 4+9/2 = 6

Значение в месте [mid] = 25

ключ в локации [mid]

Теперь мы сравниваем ключевой элемент со средним элементом. Итак (25 == 25), таким образом, мы нашли ключ в локации [mid].

Многократно деля массив и, сравнивая ключевой элемент со средним, решаем, в какой половине искать ключ.

Ниже приведены реализации скетча C++ и Java для бинарного поиска.

Реализация на С++:

Вывод данных:

Входной массив:
5 8 10 13 21 23 25 43 54 75
Введите ключ для поиска: 21
Ключ найден в ячейке 5 .

Читать также:  Хеш-таблица в C++

Реализация на Java:

Вывод данных:

Входной массив:
5 8 10 13 21 23 25 43 54 75
Введите ключ для поиска:
21
расположение ключа 5

Бинарный поиск более эффективен с точки зрения времени и корректности. Метод линейного поиска используется редко, так как он более громоздкий и медленный. Бинарный поиск намного быстрее по сравнению с линейным поиском.

Итог

Методы поиска помогают нам искать информацию, хранящуюся на компьютере, чтобы пользователь мог приступить к другим задачам обработки информации. Техника линейного поиска проста и легка, но широко не используется. Техника бинарного поиска намного быстрее и эффективнее, поэтому она и рекомендуется к использованию.

В нашей следующей статье мы подробно рассмотрим список различных методов сортировки в C++.

С Уважением, МониторБанк

Добавить комментарий