zelfs geen enkele dagkaart, wanneer we niet naar iets in ons dagelijks leven hoeven te zoeken, autosleutels, boeken, pen, mobiele lader en wat niet. Hetzelfde is het leven van een computer, er is zoveel data opgeslagen in het, dat wanneer een gebruiker vraagt om een aantal gegevens, computer moet zoeken in het geheugen om te zoeken naar de gegevens en beschikbaar te maken voor de gebruiker. En de computer heeft zijn eigen technieken om te zoeken door het geheugen snel, die u meer over in onze besturingssysteem tutorial serie kunt leren.
wat als u een programma moet schrijven om een bepaald getal in een array te zoeken? Hoe ga je het doen?
om een element in een bepaalde array te zoeken, zijn er twee populaire algoritmen beschikbaar:
- lineair zoeken
- binair zoeken
lineair zoeken
lineair zoeken is een zeer eenvoudig en eenvoudig zoekalgoritme. In lineair zoeken zoeken we een element of waarde in een bepaalde array door de array te doorlopen vanaf het begin, totdat het gewenste element of de gewenste waarde is gevonden.
het vergelijkt het te doorzoeken element met alle elementen die aanwezig zijn in de array en wanneer het element met succes overeenkomt, geeft het de index van het element in de array terug, anders geeft het -1terug.
lineair zoeken wordt toegepast op ongesorteerde of ongeordende lijsten, wanneer er minder elementen in een lijst zijn.
kenmerken van lineair zoekalgoritme
- het wordt gebruikt voor ongesorteerde en ongeordende kleine lijst van elementen.
- het heeft een tijdscomplexiteit van O (n), wat betekent dat de tijd lineair afhankelijk is van het aantal elementen, wat niet slecht is, maar ook niet zo goed.
- het heeft een zeer eenvoudige implementatie.
we zullen het lineaire zoekalgoritme in de volgende tutorial implementeren.
binair zoeken
binair zoeken wordt gebruikt met gesorteerde array of lijst. In binair zoeken, volgen we de volgende stappen:
- we beginnen met het vergelijken van het te doorzoeken element met het element in het midden van de lijst/array.
- als we een overeenkomst krijgen, geven we de index van het middelste element terug.
- als we geen overeenkomst krijgen, controleren we of het te doorzoeken element kleiner of groter is dan de waarde van het middelste element.
- als het element/getal dat gezocht moet worden groter is in waarde dan het middelste getal, dan kiezen we de elementen aan de rechterkant van het middelste element(als de lijst/array gesorteerd is, dus aan de rechterkant, zullen we alle getallen groter dan het middelste getal hebben), en beginnen we opnieuw vanaf stap 1.
- als het element / getal dat gezocht moet worden kleiner is in waarde dan het middelste getal, dan kiezen we de elementen aan de linkerkant van het middelste element en beginnen we opnieuw vanaf stap 1.
binair zoeken is nuttig als er een groot aantal elementen in een array zijn en ze zijn gesorteerd.
een noodzakelijke voorwaarde voor binair zoeken is dat de lijst / array gesorteerd moet worden.
kenmerken van binair zoeken
- het is geweldig om door grote gesorteerde arrays te zoeken.
- het heeft een tijdcomplexiteit van o (log n), wat een zeer goede tijdcomplexiteit is. We zullen dit in detail bespreken in de Binary Search tutorial.
- het heeft een eenvoudige implementatie.