Реалізації алгоритмів пошуку в Python

Автор

Запровадити пошук завжди складно, але не неможливо.

У реальному житті ми шукатимемо без шаблону. Ми просто йдемо до місць, де, на нашу думку, це може бути розміщено. У більшості випадків ми не дотримуємося жодної моделі.

Чи те саме працює у світі програмування?

Ні! існує певний шаблон для пошуку речей у програмах. У цій статті ми побачимо кілька алгоритмів, які дотримуються різних шаблонів пошуку.

У світі програмування можна знайти кілька алгоритмів. У цій статті ми обговоримо найважливіші та найчастіше використовувані алгоритми. А решту алгоритмів вам буде легко вивчити.

Пошук означає пошук елемента в масиві в цій статті.

Давайте розглянемо їх по одному.

Лінійний пошук

З назви випливає, що алгоритм лінійного пошуку дотримується лінійного шаблону для пошуку елементів у масиві. Алгоритм починає пошук елемента з початку масиву і рухається до кінця, поки не знайде елемент. Він зупиняє виконання програми, коли знаходить необхідний елемент.

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

Якщо ви уважно спостерігаєте за шаблоном пошуку, ви виявите, що час, необхідний для виконання програми, у найгіршому випадку займе O(n). Ми маємо розглянути найгіршу часову складність алгоритмів для аналізу. Отже, часова складність алгоритму дорівнює O(n).

Подивимося реалізацію алгоритму лінійного пошуку.

Реалізація лінійного пошуку

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

Давайте розглянемо кроки реалізації алгоритму лінійного пошуку.

  • Ініціалізуйте масив елементів (ваші щасливі числа).
  • Напишіть функцію з назвою search_element, яка приймає три аргументи, масив, довжину масиву та елемент, який шукають.
  • search_element(arr, n, element):
    • Ітерація по заданому масиву.
      • Перевірити, чи дорівнює поточний елемент необхідному.
      • Якщо так, поверніть True.
    • Якщо після завершення циклу функція все ще виконується, елемент відсутній у масиві. Тому повертаємо False.
  • Вивести повідомлення на основі значення, яке повертає функція search_element.
  Як змінити зображення профілю в програмі Xbox

Нарешті, напишіть код за допомогою наведених вище кроків, щоб реалізувати алгоритм лінійного пошуку.

Ви завершили реалізацію алгоритму лінійного пошуку? Я на це сподіваюся. Якщо ви виконали, перевірте перехресну перевірку за допомогою наступного коду.

Якщо ви не завершили його, не хвилюйтеся; перегляньте наведений нижче код і дізнайтеся, як ми його реалізували. Ви отримаєте його без особливих зусиль.

## 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).

Чи можемо ми ще трохи зменшити його за допомогою інших шаблонів?

Так, ми можемо. Давайте подивимося.

Двійковий пошук

Алгоритм бінарного пошуку завжди перевіряє середній елемент масиву. Цей алгоритм шукає елемент у відсортованому масиві.

Алгоритм бінарного пошуку повторює масив і перевіряє середній елемент, якщо він знайдений, а потім зупиняє програму. Інакше, якщо середній елемент менший за необхідний елемент, тоді він пропускає ліву частину масиву від середнього елемента з пошуку. Інакше, якщо середній елемент більший за потрібний, тоді права частина масиву від середнього елемента виключається з пошуку.

  Як змінити свій план Netflix

У кожній ітерації бінарний алгоритм пошуку скорочує область для пошуку елемента. Таким чином, кількість перевірок менше, ніж кількість перевірок, зроблених в алгоритмі лінійного пошуку.

Ілюстрації допомагають нам краще зрозуміти алгоритм бінарного пошуку. Давайте їх перевіримо.

Часова складність алгоритму бінарного пошуку становить O(log n). У кожній ітерації довжина області пошуку зменшується вдвічі. Він скорочується в геометричній прогресії.

Реалізація двійкового пошуку

Спочатку ми побачимо кроки для реалізації алгоритму бінарного пошуку, а потім код. Давайте розглянемо кроки для завершення реалізації алгоритму бінарного пошуку.

  • Ініціалізація масиву елементами (ваші щасливі числа)
  • Напишіть функцію під назвою search_element, яка приймає три аргументи, відсортований масив, довжину масиву та елемент для пошуку.
  • search_element(sorted_arr, n, element):
    • Ініціалізуйте змінну індексу i для ітерації масиву.
    • Далі ініціалізуйте дві змінні, щоб зберегти область пошуку масиву. Тут ми називаємо їх як початок і кінець, оскільки вони позначають індекси.
    • Повторюйте, доки i не стане меншим за довжину масиву.
      • Обчисліть середній індекс області пошуку, використовуючи початкове та кінцеве значення. Це буде (початок + кінець) // 2.
      • Перевірте, чи дорівнює середній індексований елемент із області пошуку потрібному елементу чи ні.
      • Якщо так, поверніть True.
      • Інакше, якщо середній індексований елемент менший за необхідний елемент, тоді перемістіть початковий індекс області пошуку до середини + 1.
      • Інакше, якщо середній індексований елемент більший за необхідний елемент, тоді перемістіть кінцевий індекс області пошуку до середини – 1.
      • Збільшити індекс масиву i.
    • Якщо після завершення циклу функція все ще виконується, елемент відсутній у масиві. Тому повертаємо False.
  • Вивести повідомлення на основі значення, яке повертає функція search_element.
  6 найкращих хостингів серверів Arma Reforger для плавного ігрового процесу

Спробуйте написати код, схожий на реалізацію алгоритму лінійного пошуку.

…

Ви отримали код?

Так, порівняйте його з наведеним нижче кодом. Ні, не хвилюйтеся; зрозуміти реалізацію за допомогою наведеного нижче коду.

## 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.

Далі ознайомтеся з популярним програмним забезпеченням для самостійного пошуку.

Щасливого кодування 🙂 🧑‍💻