Вы когда-нибудь видели красивую девушку или красивого мальчика и пытались найти ее/его в Facebook или Instagram? Довольно тяжелая работа, верно? Вы ничего не знаете, даже имени человека, которого вы ищете, но, программисты, вы когда-нибудь задумывались, как эта панель поиска ищет этого человека для вас?
Да! Они используют различные алгоритмы поиска, но сегодня мы узнаем о некоторых основных алгоритмах поиска.
Рассмотрим сценарий, вы обнаружили, что кто-то из ваших одноклассников украл ваши часы, но вы не знаете, кто, что вы будете делать?
Конечно, вам нужно будет проверить все сумки, такой подход к поиску называется Линейный поиск.
Линейный поиск:
Метод поиска, при котором вы сравниваете свой элемент с каждым элементом массива или списка данных, называется линейным поиском.
Давайте посмотрим, как выглядит программа линейного поиска:
Сколько времени занимает эта программа? хорошо предположим, что информация, предоставленная вам, была неверной, никто из вашего класса не украл ее, тогда время, затраченное вами на проверку всех сумок, будет называться наихудшим сценарием.
Программно это можно показать так: для Nвремя, необходимое для наихудшего случая, будет O(n) как он будет сравниваться с каждым элементом.
Давайте двигаться вперед, теперь учтите, что вы понимаете, что мальчик из вашего класса украл ваши часы, поэтому ваша проблема делится пополам, теперь вы снова узнали, что мальчик из 3-го ряда украл их, проблема снова уменьшилась.
Бинарный поиск:
Метод поиска, при котором задача делится пополам из-за некоторого условия, называется бинарным поиском. этот подход также называется разделяй и властвуй.
Итак, давайте посмотрим на программу бинарного поиска:
Сколько времени это занимает? Ну, в каждом круге мы делим алгоритм пополам, поэтому для ввода N время будет N/2 . Следовательно, сложность в наихудшем случае составляет O(logn). (P.S.: Алгоритму бинарного поиска нужны отсортированные данные.)
Это все! Да, теперь вы знаете, как выполнять операцию поиска.
Получите код со страницы: https://github.com/agarwalamn/algoritms/tree/master/searching
(Это был мой первый пост в блоге, поэтому предложения и критика всегда приветствуются)
