Implementering af søgning er altid udfordrende, men ikke umuligt.
I det virkelige liv vil vi søge i intet mønster. Vi går bare hen til de steder, hvor vi tænker, at den kan placeres. Vi følger ikke noget mønster i de fleste tilfælde.
Virker det samme i programmeringsverdenen?
Ingen! der er et eller andet mønster for at søge efter ting i programmer. Vi kommer til at se nogle algoritmer, der følger forskellige mønstre for søgning i denne artikel.
Der er flere algoritmer, som vi kan finde i programmeringsverdenen. Vi vil diskutere de vigtigste og mest brugte algoritmer i denne artikel. Og resten af algoritmerne vil være et stykke kage for dig at lære.
Søgning refererer til at søge efter et element i arrayet i denne artikel.
Lad os se dem én efter én.
Indholdsfortegnelse
Lineær søgning
Navnet antyder, at den lineære søgealgoritme følger det lineære mønster for at søge i elementerne i en matrix. Algoritmen begynder at søge i elementet fra begyndelsen af arrayet og bevæger sig til slutningen, indtil den finder elementet. Den stopper udførelse af programmet, når den finder det nødvendige element.
Lad os illustrere de lineære søgealgoritmer med nogle fede illustrationer for en bedre forståelse af algoritmen.
Hvis du nøje observerer søgemønsteret, vil du opdage, at den tid, det tager for programmets udførelse, vil tage O(n) i værste fald. Vi er nødt til at overveje den værst tænkelige tidskompleksitet af de algoritmer, der skal analyseres. Derfor er tidskompleksiteten af algoritmen O(n).
Lad os se implementeringen af den lineære søgealgoritme.
Lineær søgeimplementering
Nu har du en god forståelse af den lineære søgealgoritme. Det er tid til at gøre vores hænder beskidte med noget kode. Lad os først se trinene til at implementere den lineære søgning. Så prøver du at kode det. Du skal ikke bekymre dig om, selvom du ikke kan; Jeg giver dig koden bagefter.
Lad os se trinene til at implementere den lineære søgealgoritme.
- Initialiser en række elementer (dine lykketal).
- Skriv en funktion kaldet search_element, som accepterer tre argumenter, matrix, længden af matrixen og element, der skal søges i.
- søgeelement(arr, n, element):
- Gentag over det givne array.
- Kontroller, om det aktuelle element er lig med det nødvendige element.
- Hvis ja, så returner True.
- Efter at have afsluttet løkken, hvis udførelsen stadig er i funktionen, er elementet ikke til stede i arrayet. Derfor returnerer False.
- Gentag over det givne array.
- Udskriv meddelelsen baseret på returværdien af funktionen søgeelement.
Skriv endelig koden ved hjælp af ovenstående trin for at implementere den lineære søgealgoritme.
Fuldførte du implementeringen af den lineære søgealgoritme? Det håber jeg. Hvis du har fuldført, så krydstjek med følgende kode.
Hvis du ikke har fuldført det, så fortvivl ikke,; se nedenstående kode og lær hvordan vi implementerede den. Du får det uden stor indsats.
## 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")
Udfør først programmet med et element, der er til stede i arrayet. Og dernæst skal du udføre det med et element, der ikke er til stede i arrayet.
Tidskompleksiteten af den lineære søgealgoritme er O(n).
Kan vi reducere det lidt yderligere med forskellige mønstre?
Ja, det kan vi. Lad os se det.
Binær søgning
Den binære søgealgoritme kontrollerer altid det midterste element i arrayet. Denne algoritme søger efter elementet i et sorteret array.
Den binære søgealgoritme itererer over arrayet og kontrollerer det midterste element, hvis det findes, og stopper derefter programmet. Ellers, hvis det midterste element er mindre end det påkrævede element, udelader det den venstre del af arrayet fra det midterste element fra at søge. Ellers, hvis det midterste element er større end det påkrævede element, udelader det den højre del af arrayet fra det midterste element fra at søge.
I hver iteration skærer den binære søgealgoritme ned området for at søge i elementet. Så antallet af kontroller er mindre end antallet af kontroller foretaget i den lineære søgealgoritme.
Illustrationer hjælper os med bedre at forstå den binære søgealgoritme. Lad os tjekke dem.
Tidskompleksiteten af den binære søgealgoritme er O(log n). I hver iteration reduceres længden af søgeområdet med det halve. Det reduceres eksponentielt.
Implementering af binær søgning
Først vil vi se trinene til at implementere den binære søgealgoritme og derefter koden. Lad os se trinene til at fuldføre implementeringen af den binære søgealgoritme.
- Initialiser arrayet med elementer (dine lykketal)
- Skriv en funktion kaldet search_element, som accepterer tre argumenter, sorteret array, længden af arrayet og element, der skal søges i.
- søgeelement(sorteret_arr, n, element):
- Initialiser indeksvariablen i for array-iteration.
- Derefter initialiseres to variabler for at bevare søgeområdet i arrayet. Her kalder vi dem for at starte og slutte, da de angiver indekser.
- Gentag indtil i er mindre end længden af arrayet.
- Beregn det midterste indeks for søgeområdet ved hjælp af start- og slutværdierne. Det vil være (start + slut) // 2.
- Kontroller, om det midterste indekserede element fra søgeområdet er lig med det nødvendige element eller ej.
- Hvis ja, så returner True.
- Ellers, hvis det midterste indekserede element er mindre end det påkrævede element, skal du flytte startindekset for søgeområdet til midten + 1.
- Ellers, hvis det midterste indekserede element er større end det påkrævede element, skal du flytte søgeområdets slutindeks til midten – 1.
- Forøg indekset for arrayet i.
- Efter at have afsluttet løkken, hvis udførelsen stadig er i funktionen, er elementet ikke til stede i arrayet. Derfor returnerer False.
- Udskriv meddelelsen baseret på returværdien af funktionen søgeelement.
Prøv at skrive koden svarende til implementeringen af den lineære søgealgoritme.
…
Fik du koden?
Ja, sammenlign det med nedenstående kode. Nej, bare rolig; forstå implementeringen med nedenstående kode.
## 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 forskellige tilfælde, hvor elementet er til stede og ikke til stede i nogle tilfælde.
Konklusion
Den binære søgealgoritme er langt mere effektiv end den lineære søgealgoritme. Vi skal sortere arrayet for binær søgealgoritme er ikke tilfældet i den lineære søgealgoritme. Sortering tager noget tid. Men brug af effektive algoritmer til sortering vil danne en god kombination med den binære søgealgoritme.
Nu har du et godt kendskab til de mest udbredte algoritmer i Python.
Find derefter ud af noget af det populære selvhostede søgesoftware.
God kodning 🙂 🧑💻