Å implementere søk er alltid utfordrende, men ikke umulig.
I det virkelige liv vil vi ikke søke i noe mønster. Vi går bare til de stedene der vi tror den kan plasseres. Vi følger ikke noe mønster i de fleste tilfeller.
Fungerer det samme i programmeringsverdenen?
Nei! det må et mønster for å søke etter ting i programmer. Vi skal se noen algoritmer som følger forskjellige mønstre for søk i denne artikkelen.
Det er flere algoritmer vi kan finne i programmeringsverdenen. Vi skal diskutere de viktigste og mest brukte algoritmene i denne artikkelen. Og resten av algoritmene vil være et stykke kake for deg å lære.
Søking refererer til å søke etter et element i matrisen i denne artikkelen.
La oss se dem en etter en.
Innholdsfortegnelse
Lineært søk
Navnet antyder at den lineære søkealgoritmen følger det lineære mønsteret for å søke i elementene i en matrise. Algoritmen begynner å søke i elementet fra begynnelsen av matrisen og beveger seg til slutten til den finner elementet. Den stopper kjøringen av programmet når den finner det nødvendige elementet.
La oss illustrere de lineære søkealgoritmene med noen kule illustrasjoner for en bedre forståelse av algoritmen.
Hvis du nøye observerer søkemønsteret, vil du finne at tiden det tar før programmets utførelse vil ta O(n) i verste fall. Vi må vurdere den verste tilfelle tidskompleksiteten til algoritmene som skal analyseres. Derfor er tidskompleksiteten til algoritmen O(n).
La oss se implementeringen av den lineære søkealgoritmen.
Lineær søkeimplementering
Nå har du en god forståelse av den lineære søkealgoritmen. Det er på tide å gjøre hendene skitne med litt kode. La oss først se fremgangsmåten for å implementere det lineære søket. Så prøver du å kode den. Ikke bekymre deg selv om du ikke kan; Jeg vil gi deg koden etterpå.
La oss se trinnene for å implementere den lineære søkealgoritmen.
- Initialiser en rekke elementer (lykketallene dine).
- Skriv en funksjon kalt search_element, som godtar tre argumenter, matrise, lengde på matrisen og element som skal søkes i.
- søkeelement(arr, n, element):
- Iterer over den gitte matrisen.
- Sjekk om det gjeldende elementet er lik det nødvendige elementet.
- Hvis ja, returner True.
- Etter å ha fullført loopen, hvis utførelsen fortsatt er i funksjonen, er ikke elementet tilstede i matrisen. Returner derfor False.
- Iterer over den gitte matrisen.
- Skriv ut meldingen basert på returverdien til funksjonen søkeelement.
Til slutt, skriv koden ved hjelp av trinnene ovenfor for å implementere den lineære søkealgoritmen.
Fullførte du implementeringen av den lineære søkealgoritmen? Jeg håper det. Hvis du fullførte, krysssjekk med følgende kode.
Hvis du ikke fullførte det, ikke bekymre deg,; se koden nedenfor og lær hvordan vi implementerte den. Du vil få det uten mye anstrengelse.
## 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")
Kjør først programmet med et element som er tilstede i matrisen. Og deretter, utfør den med et element som ikke er til stede i matrisen.
Tidskompleksiteten til den lineære søkealgoritmen er O(n).
Kan vi redusere det litt ytterligere med forskjellige mønstre?
Ja, det kan vi. La oss se det.
Binært søk
Den binære søkealgoritmen sjekker alltid midtelementet i matrisen. Denne algoritmen søker etter elementet i en sortert matrise.
Den binære søkealgoritmen itererer over matrisen og sjekker midtelementet, hvis det finnes, og stopper deretter programmet. Ellers hvis det midterste elementet er mindre enn det nødvendige elementet, utelater det den venstre delen av matrisen fra midtelementet fra å søke. Ellers hvis det midterste elementet er større enn det nødvendige elementet, utelater det den høyre delen av matrisen fra midtelementet fra å søke.
I hver iterasjon kutter den binære søkealgoritmen ned området for å søke i elementet. Så antallet kontroller er mindre enn antallet kontroller som er utført i den lineære søkealgoritmen.
Illustrasjoner hjelper oss med å bedre forstå den binære søkealgoritmen. La oss sjekke dem.
Tidskompleksiteten til den binære søkealgoritmen er O(log n). I hver iterasjon blir lengden på søkeområdet halvert. Det reduseres eksponentielt.
Binær søkeimplementering
Først vil vi se trinnene for å implementere den binære søkealgoritmen og deretter koden. La oss se trinnene for å fullføre implementeringen av den binære søkealgoritmen.
- Initialiser matrisen med elementer (lykketallene dine)
- Skriv en funksjon kalt search_element, som godtar tre argumenter, sortert matrise, lengde på matrisen og element som skal søkes i.
- søkeelement(sortert_arr, n, element):
- Initialiser indeksvariabelen i for array-iterasjon.
- Deretter initialiserer du to variabler for å opprettholde søkeområdet til matrisen. Her kaller vi dem for start og slutt ettersom de indikerer indekser.
- Iterer til i-en er mindre enn lengden på matrisen.
- Beregn midtindeksen til søkeområdet ved å bruke start- og sluttverdiene. Det vil være (start + slutt) // 2.
- Sjekk om det midterste indekserte elementet fra søkeområdet er lik det nødvendige elementet eller ikke.
- Hvis ja, returner True.
- Ellers hvis det midterste indekserte elementet er mindre enn det nødvendige elementet, flytter du startindeksen til søkeområdet til midten + 1.
- Ellers hvis det midterste indekserte elementet er større enn det nødvendige elementet, flytter du sluttindeksen til søkeområdet til midten – 1.
- Øk indeksen til matrisen i.
- Etter å ha fullført loopen, hvis utførelsen fortsatt er i funksjonen, er ikke elementet tilstede i matrisen. Returner derfor False.
- Skriv ut meldingen basert på returverdien til funksjonen søkeelement.
Prøv å skrive koden som ligner på implementeringen av lineær søkealgoritme.
…
Fikk du koden?
Ja, sammenlign det med koden nedenfor. Nei, ikke bekymre deg; forstå implementeringen med koden nedenfor.
## 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")
Test koden med forskjellige tilfeller der elementet er tilstede og ikke til stede i noen tilfeller.
Konklusjon
Den binære søkealgoritmen er mye mer effektiv enn den lineære søkealgoritmen. Vi trenger å sortere matrisen for binær søkealgoritme er ikke tilfelle i den lineære søkealgoritmen. Sortering tar litt tid. Men å bruke effektive algoritmer for sortering vil danne en god kombinasjon med den binære søkealgoritmen.
Nå har du god kunnskap om de mest brukte algoritmene i Python.
Deretter kan du finne ut noen av de populære selvhostede søkeprogramvarene.
Lykke til med koding 🙂 🧑💻