Реализации алгоритмов поиска в Python

Реализация поиска всегда сложна, но не невозможна.

В реальной жизни мы будем искать без шаблона. Мы просто идем в места, где мы думаем, что это может быть размещено. В большинстве случаев мы не следуем какой-либо схеме.

Работает ли то же самое в мире программирования?

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

Есть несколько алгоритмов, которые мы можем найти в мире программирования. В этой статье мы обсудим наиболее важные и наиболее часто используемые алгоритмы. А остальные алгоритмы вам не составит труда выучить.

В этой статье под поиском понимается поиск элемента в массиве.

Давайте посмотрим их один за другим.

Оглавление

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

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

Давайте проиллюстрируем алгоритмы линейного поиска несколькими классными иллюстрациями для лучшего понимания алгоритма.

Если вы внимательно понаблюдаете за шаблоном поиска, то обнаружите, что время выполнения программы в худшем случае составит O(n). Мы должны учитывать наихудшую временную сложность алгоритмов для анализа. Следовательно, временная сложность алгоритма равна O(n).

Давайте посмотрим на реализацию алгоритма линейного поиска.

Реализация линейного поиска

Теперь вы хорошо понимаете алгоритм линейного поиска. Пришло время испачкать руки кодом. Давайте сначала посмотрим, как реализовать линейный поиск. Затем вы пытаетесь закодировать его. Не беспокойтесь, даже если вы не можете; Я дам вам код позже.

Давайте посмотрим, как реализовать алгоритм линейного поиска.

Инициализируйте массив элементов (ваши счастливые числа).
Напишите функцию с именем search_element, которая принимает три аргумента, массив, длину массива и элемент для поиска.
search_element(обр, n, элемент):
- Перебрать заданный массив.
  - Проверить, равен ли текущий элемент требуемому элементу.
  - Если да, то вернуть True.
- После завершения цикла, если выполнение все еще находится в функции, то элемент отсутствует в массиве. Следовательно, верните False.
Напечатайте сообщение на основе возвращаемого значения функции search_element.

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

Вы завершили реализацию алгоритма линейного поиска? Я надеюсь, что это так. Если вы завершили, перепроверьте с помощью следующего кода.

Если вы не заполнили его, не волнуйтесь; посмотрите приведенный ниже код и узнайте, как мы его реализовали. Вы получите его без особых усилий.

## searching function
def search_element(arr, n, element):

	## iterating through the array
	for i in range(n):

		## checking the current element with required element
		if arr[i] == element:
			## returning True on match
			return True

	## element is not found hence the execution comes here
	return False


if __name__ == '__main__':
	## initializing the array, length, and element to be searched
	arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	n = 10
	element_to_be_searched = 6
	# element_to_be_searched = 11

	if search_element(arr, n, element_to_be_searched):
		print(element_to_be_searched, "is found")
	else:
		print(element_to_be_searched, "is not found")

Сначала выполните программу с элементом, присутствующим в массиве. А затем выполните его с элементом, которого нет в массиве.

Временная сложность алгоритма линейного поиска составляет O(n).

Можем ли мы еще немного уменьшить его с помощью других шаблонов?

Да, мы можем. Давай увидим это.

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

Алгоритм бинарного поиска всегда проверяет средний элемент массива. Этот алгоритм ищет элемент в отсортированном массиве.

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

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

Иллюстрации помогают нам лучше понять алгоритм бинарного поиска. Давайте проверим их.

Временная сложность алгоритма бинарного поиска составляет O(log n). На каждой итерации длина области поиска уменьшается вдвое. Он сокращается в геометрической прогрессии.

Реализация бинарного поиска

Сначала мы увидим шаги по реализации алгоритма бинарного поиска, а затем код. Давайте посмотрим, как завершить реализацию алгоритма бинарного поиска.

Инициализируйте массив элементами (ваши счастливые числа)
Напишите функцию с именем search_element, которая принимает три аргумента, отсортированный массив, длину массива и элемент для поиска.
search_element(sorted_arr, n, элемент):
- Инициализируйте индексную переменную i для итерации массива.
- Затем инициализируйте две переменные, чтобы поддерживать область поиска в массиве. Здесь мы называем их как начало и конец, поскольку они указывают индексы.
- Повторяйте до тех пор, пока i не станет меньше длины массива.
  - Вычислите средний индекс области поиска, используя начальное и конечное значения. Это будет (начало + конец) // 2.
  - Проверяем, равен ли средний индексированный элемент из области поиска искомому элементу или нет.
  - Если да, то вернуть True.
  - В противном случае, если средний индексированный элемент меньше требуемого элемента, то переместите начальный индекс области поиска на средний + 1.
  - В противном случае, если средний проиндексированный элемент больше требуемого элемента, то переместите конечный индекс области поиска в средний — 1.
  - Увеличить индекс массива i.
- После завершения цикла, если выполнение все еще находится в функции, то элемент отсутствует в массиве. Следовательно, верните False.
Напечатайте сообщение на основе возвращаемого значения функции search_element.

Попробуйте написать код, аналогичный реализации алгоритма линейного поиска.

…

Вы получили код?

Да, сравните его с приведенным ниже кодом. Нет, не волнуйтесь; понять реализацию с приведенным ниже кодом.

## searching function
def search_element(sorted_arr, n, element):

	## array index for iteration
	i = 0

	## variables to track the search area
	## initializing them with start and end indexes
	start = 0
	end = n - 1

	## iterating over the array
	while i < n:
		## getting the index of the middle element
		middle = (start + end) // 2

		## checking the middle element with required element
		if sorted_arr[middle] == element:
			## returning True since the element is in the array
			return True
		elif sorted_arr[middle] < element:
			## moving the start index of the search area to right
			start = middle + 1
		else:
			## moving the end index of the search area to left
			end = middle - 1
		i += 1
	return False


if __name__ == '__main__':
	## initializing the array, length, and element to be searched
	arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	n = 10
	element_to_be_searched = 9
	# element_to_be_searched = 11

	if search_element(arr, n, element_to_be_searched):
		print(element_to_be_searched, "is found")
	else:
		print(element_to_be_searched, "is not found")

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

Вывод

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

Теперь вы хорошо знаете наиболее широко используемые алгоритмы в Python.

Затем узнайте о некоторых популярных программах для самостоятельного поиска.

Удачного кодирования 🙂 🧑‍💻