Имплементације алгоритама претраживања у Питхон-у

by
Tweet
Share
Share
Pin

Спровођење претраге је увек изазовно, али није немогуће.

У стварном животу, тражићемо без обрасца. Само идемо на места где мислимо да би то могло бити постављено. У већини случајева не следимо никакав образац.

Да ли иста ствар функционише у свету програмирања?

Не! постоји неки образац за претраживање ствари у програмима. У овом чланку ћемо видети неке алгоритме који прате различите обрасце за претрагу.

Постоји више алгоритама које можемо пронаћи у свету програмирања. У овом чланку ћемо разговарати о најважнијим и најчешће коришћеним алгоритмима. А остали алгоритми ће вам бити лаки за учење.

Претраживање се односи на претраживање елемента у низу у овом чланку.

Хајде да их видимо једног по једног.

Линеар Сеарцх

Име сугерише да алгоритам линеарне претраге прати линеарни образац за претрагу елемената у низу. Алгоритам почиње да тражи елемент од почетка низа и креће се до краја док не пронађе елемент. Зауставља извршавање програма када пронађе тражени елемент.

Хајде да илуструјемо алгоритме линеарне претраге са неким сјајним илустрацијама за боље разумевање алгоритма.

Ако пажљиво посматрате образац претраге, видећете да ће време које је потребно за извршавање програма трајати О(н) у најгорем случају. Морамо узети у обзир временску сложеност алгоритама у најгорем случају за анализу. Отуда је временска сложеност алгоритма О(н).

Хајде да видимо имплементацију алгоритма линеарне претраге.

Имплементација линеарне претраге

Сада добро разумете алгоритам линеарне претраге. Време је да запрљамо руке неком шифром. Хајде да прво погледамо кораке за имплементацију линеарне претраге. Онда покушате да га кодирате. Не брините чак и ако не можете; Касније ћу вам дати код.

  Водич за увод у АВС ДоцументДБ

Хајде да видимо кораке за имплементацију алгоритма линеарне претраге.

  • Иницијализујте низ елемената (ваши срећни бројеви).
  • Напишите функцију под називом сеарцх_елемент, која прихвата три аргумента, низ, дужину низа и елемент који се тражи.
  • сеарцх_елемент(арр, н, елемент):
    • Итерирајте преко датог низа.
      • Проверите да ли је тренутни елемент једнак траженом елементу.
      • Ако јесте, онда вратите Труе.
    • Након завршетка петље, ако је извршење још увек у функцији, онда елемент није присутан у низу. Стога вратите Фалсе.
  • Одштампајте поруку на основу повратне вредности функције сеарцх_елемент.

На крају, напишите код уз помоћ горњих корака да бисте имплементирали алгоритам линеарне претраге.

Да ли сте завршили имплементацију алгоритма линеарне претраге? Надам се. Ако сте завршили, онда унакрсно проверите следећи код.

Ако га нисте довршили, не брините; погледајте код у наставку и сазнајте како смо га имплементирали. Добићете га без много труда.

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

Прво, извршите програм са елементом који је присутан у низу. Затим га извршите са елементом који није присутан у низу.

Временска сложеност алгоритма линеарне претраге је О(н).

Можемо ли га још мало смањити различитим обрасцима?

Да, можемо. Дај да видимо.

Бинарно претраживање

Алгоритам бинарне претраге увек проверава средњи елемент низа. Овај алгоритам претражује елемент у сортираном низу.

Алгоритам бинарне претраге прелази низ низ и проверава средњи елемент, ако је пронађен, а затим зауставља програм. Иначе, ако је средњи елемент мањи од захтеваног елемента, онда изоставља леви део низа из средњег елемента из претраживања. Иначе, ако је средњи елемент већи од потребног елемента, онда изоставља десни део низа из средњег елемента из претраживања.

  Како добити лајкове на ТикТок-у без преузимања апликација

У свакој итерацији, алгоритам бинарне претраге смањује област за претрагу елемента. Дакле, број провера је мањи од броја провера направљених у алгоритму линеарне претраге.

Илустрације нам помажу да боље разумемо алгоритам бинарног претраживања. Хајде да их проверимо.

Временска сложеност алгоритма бинарне претраге је О(лог н). У свакој итерацији, дужина области претраге се смањује за половину. Експоненцијално се смањује.

Имплементација бинарног претраживања

Прво ћемо видети кораке за имплементацију алгоритма бинарног претраживања, а затим и код. Хајде да видимо кораке за завршетак имплементације алгоритма бинарног претраживања.

  • Иницијализујте низ са елементима (ваши срећни бројеви)
  • Напишите функцију под називом сеарцх_елемент, која прихвата три аргумента, сортирани низ, дужину низа и елемент који се тражи.
  • сеарцх_елемент(сортед_арр, н, елемент):
    • Иницијализујте променљиву индекса и за итерацију низа.
    • Затим иницијализујте две променљиве да бисте одржали област претраживања низа. Овде их називамо као почетак и крај јер означавају индексе.
    • Итерирајте све док и не буде мање од дужине низа.
      • Израчунајте средњи индекс области претраге користећи почетну и крајњу вредност. То ће бити (почетак + крај) // 2.
      • Проверите да ли је средњи индексирани елемент из области претраге једнак траженом елементу или не.
      • Ако јесте, онда вратите Труе.
      • Иначе, ако је средњи индексирани елемент мањи од потребног елемента, онда померите почетни индекс области за претрагу на средину + 1.
      • У супротном, ако је средњи индексирани елемент већи од потребног елемента, онда померите крајњи индекс области за претрагу на средину – 1.
      • Повећајте индекс низа и.
    • Након завршетка петље, ако је извршење још увек у функцији, онда елемент није присутан у низу. Стога вратите Фалсе.
  • Одштампајте поруку на основу повратне вредности функције сеарцх_елемент.
  Како уклонити Инстаграм филтер са фотографије

Покушајте да напишете код сличан имплементацији алгоритма линеарне претраге.

…

Јесте ли добили код?

Да, упоредите га са кодом испод. Не, не брини; разумете имплементацију помоћу кода у наставку.

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

Тестирајте код са различитим случајевима где је елемент присутан, а у неким случајевима није присутан.

Закључак

Бинарни алгоритам претраге је много ефикаснији од алгоритма линеарне претраге. Морамо да сортирамо низ за алгоритам бинарног претраживања није случај у алгоритму линеарне претраге. Сортирање траје неко време. Али, коришћење ефикасних алгоритама за сортирање ће формирати добру комбинацију са алгоритмом бинарног претраживања.

Сада имате добро познавање најчешће коришћених алгоритама у Питхон-у.

Затим сазнајте неке од популарних софтвера за претрагу који се сами хостују.

Срећно кодирање 🙂 🧑‍💻