Реализации на алгоритми за търсене в Python

Внедряването на търсене винаги е предизвикателство, но не и невъзможно.

В реалния живот няма да търсим по никакъв модел. Просто отиваме на местата, където смятаме, че може да бъде поставен. В повечето случаи не следваме никакъв модел.

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

Не! има някакъв модел за търсене на неща в програмите. В тази статия ще видим някои алгоритми, които следват различни модели за търсене.

Има множество алгоритми, които можем да намерим в света на програмирането. В тази статия ще обсъдим най-важните и най-често използвани алгоритми. А останалите алгоритми ще бъдат лесни за учене.

Търсенето се отнася за търсене на елемент в масива в тази статия.

Нека ги видим един по един.

Линейно търсене

Името подсказва, че алгоритъмът за линейно търсене следва линейния модел за търсене на елементите в масив. Алгоритъмът започва да търси елемента от началото на масива и се придвижва към края, докато намери елемента. Той спира изпълнението на програмата, когато намери необходимия елемент.

Нека да илюстрираме алгоритмите за линейно търсене с някои готини илюстрации за по-добро разбиране на алгоритъма.

Ако внимателно наблюдавате модела на търсене, ще откриете, че времето, необходимо за изпълнение на програмата, ще отнеме O(n) в най-лошия случай. Трябва да вземем предвид времевата сложност на алгоритмите за анализ в най-лошия случай. Следователно времевата сложност на алгоритъма е O(n).

Нека да видим изпълнението на алгоритъма за линейно търсене.

Внедряване на линейно търсене

Сега разбирате добре алгоритъма за линейно търсене. Време е да си изцапаме ръцете с малко код. Нека първо да видим стъпките за прилагане на линейното търсене. След това се опитвате да го кодирате. Не се притеснявайте дори и да не можете; Ще ви дам кода след това.

Нека видим стъпките за прилагане на алгоритъма за линейно търсене.

  • Инициализирайте масив от елементи (вашите щастливи числа).
  • Напишете функция, наречена search_element, която приема три аргумента, масив, дължина на масива и елемент за търсене.
  • search_element(arr, n, element):
    • Итерация върху дадения масив.
      • Проверете дали текущият елемент е равен на необходимия елемент.
      • Ако да, тогава върнете True.
    • След завършване на цикъла, ако изпълнението все още е във функцията, тогава елементът не присъства в масива. Следователно връща False.
  • Отпечатайте съобщението въз основа на върнатата стойност на функцията search_element.
  26 най-добрия софтуер за 3D моделиране

Накрая напишете кода с помощта на горните стъпки, за да приложите алгоритъма за линейно търсене.

Завършихте ли внедряването на алгоритъма за линейно търсене? Надявам се. Ако сте попълнили, проверете със следния код.

Ако не сте го завършили, не се притеснявайте; вижте кода по-долу и научете как го внедрихме. Ще го получите без много усилия.

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

Можем ли да го намалим още малко с различни модели?

Да, можем. Нека го видим.

Двоично търсене

Алгоритъмът за двоично търсене винаги проверява средния елемент на масива. Този алгоритъм търси елемента в сортиран масив.

Алгоритъмът за двоично търсене обхожда масива и проверява средния елемент, ако бъде намерен, след което спира програмата. В противен случай, ако средният елемент е по-малък от необходимия елемент, тогава той пропуска лявата част на масива от средния елемент от търсенето. В противен случай, ако средният елемент е по-голям от необходимия елемент, тогава той пропуска дясната част на масива от средния елемент от търсенето.

  Можете ли да закупите скинове за събития в Apex Legends?

При всяка итерация алгоритъмът за двоично търсене намалява областта за търсене на елемента. Така че броят на проверките е по-малък от броя на проверките, направени в алгоритъма за линейно търсене.

Илюстрациите ни помагат да разберем по-добре алгоритъма за двоично търсене. Да ги проверим.

Времевата сложност на алгоритъма за двоично търсене е O(log n). При всяка итерация дължината на зоната за търсене намалява наполовина. Намалява експоненциално.

Внедряване на двоично търсене

Първо ще видим стъпките за прилагане на алгоритъма за двоично търсене и след това кода. Нека видим стъпките за завършване на внедряването на алгоритъма за двоично търсене.

  • Инициализирайте масива с елементи (вашите щастливи числа)
  • Напишете функция, наречена search_element, която приема три аргумента, сортиран масив, дължина на масива и елемент за търсене.
  • search_element(sorted_arr, n, element):
    • Инициализирайте индексната променлива i за итерация на масива.
    • След това инициализирайте две променливи, за да поддържате областта за търсене на масива. Тук ги наричаме за начало и край, тъй като показват индекси.
    • Повторете, докато i стане по-малко от дължината на масива.
      • Изчислете средния индекс на областта за търсене, като използвате началната и крайната стойност. Това ще бъде (начало + край) // 2.
      • Проверете дали средният индексиран елемент от областта за търсене е равен на търсения елемент или не.
      • Ако да, тогава върнете True.
      • В противен случай, ако средният индексиран елемент е по-малък от необходимия елемент, тогава преместете началния индекс на областта за търсене в средата + 1.
      • В противен случай, ако средният индексиран елемент е по-голям от необходимия елемент, тогава преместете крайния индекс на областта за търсене в средата – 1.
      • Увеличете индекса на масива i.
    • След завършване на цикъла, ако изпълнението все още е във функцията, тогава елементът не присъства в масива. Следователно връща False.
  • Отпечатайте съобщението въз основа на върнатата стойност на функцията search_element.

Опитайте се да напишете кода, подобен на реализацията на алгоритъма за линейно търсене.

  9 приложения за хора с ADHD

Получихте ли кода?

Да, сравнете го с кода по-долу. Не, не се притеснявайте; разберете изпълнението с кода по-долу.

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

След това разберете някои от популярния самостоятелно хостван софтуер за търсене.

Приятно кодиране 🙂 🧑‍💻

x