Verschil tussen lineair zoeken en binair zoeken

2019

Lineair zoeken en binair zoeken zijn de twee methoden die worden gebruikt in arrays voor het doorzoeken van de elementen. Zoeken is een proces van het vinden van een element binnen de lijst met elementen die in willekeurige volgorde of willekeurig zijn opgeslagen.

Het belangrijkste verschil tussen lineair zoeken en binair zoeken is dat binair zoeken minder tijd kost om een element uit de gesorteerde lijst met elementen te doorzoeken. Dus wordt geconcludeerd dat de efficiëntie van binaire zoekmethode groter is dan lineair zoeken.

Een ander verschil tussen beide is dat er een voorwaarde is voor de binaire zoekopdracht, dat wil zeggen dat de elementen moeten worden gesorteerd, terwijl bij lineair zoeken er geen dergelijke vereiste is. Hoewel beide zoekmethoden verschillende technieken gebruiken die hieronder worden besproken.

Vergelijkingstabel

Basis voor vergelijking	Lineair zoeken	Binaire zoekopdracht
Tijd complexiteit	OP)	O (log `₂` N)
Beste case-time	Eerste element O (1)	Middenelement O (1)
Vereiste voor een array	Niet nodig	Matrix moet in gesorteerde volgorde zijn
Het ergste geval voor N aantal elementen	N-vergelijkingen zijn vereist	Kan concluderen na alleen log `₂` N-vergelijkingen
Kan worden geïmplementeerd op	Array en gekoppelde lijst	Kan niet direct worden geïmplementeerd op gekoppelde lijst
Plaats de bewerking	Gemakkelijk ingevoegd aan het einde van de lijst	Vereisen dat de verwerking op de juiste plaats wordt ingevoegd om een gesorteerde lijst te onderhouden.
Algoritme type	Iteratief van aard	Verdeel en heers in de natuur
Bruikbaarheid	Eenvoudig te gebruiken en geen behoefte aan bestelde elementen.	Hoe dan ook, lastig algoritme en elementen moeten op volgorde worden georganiseerd.
Lijnen met code	Minder	Meer

Definitie van lineair zoeken

Bij een lineaire zoekopdracht wordt elk element van een array één voor één opgehaald in een logische volgorde en gecontroleerd of dit element wel of niet gewenst is. Een zoekopdracht zal niet succesvol zijn als alle elementen worden geopend en het gewenste element niet wordt gevonden. In het ergste geval, het aantal van een gemiddeld geval dat we mogelijk de helft van de grootte van de array moeten scannen (n / 2).

Daarom kan lineair zoeken worden gedefinieerd als de techniek die de reeks achtereenvolgens doorloopt om het gegeven item te lokaliseren. Het onderstaande programma illustreert het zoeken naar een element in de array met behulp van zoeken.

Efficiëntie van lineair zoeken

Het tijdverbruik of het aantal vergelijkingen dat is gemaakt bij het doorzoeken van een record in een zoektabel, bepaalt de efficiëntie van de techniek. Als de gewenste record op de eerste positie van de zoektabel aanwezig is, wordt slechts één vergelijking gemaakt. Wanneer de gewenste record de laatste is, moeten n vergelijkingen worden gemaakt. Als de record ergens in de zoektabel moet worden weergegeven, is het aantal vergelijkingen gemiddeld (n + 1/2). Het slechtste geval efficiëntie van deze techniek is O (n) staat voor de volgorde van uitvoering.

C Programmeer een element met een lineaire zoektechniek.

 # include # include void main () {int a [100], n, i, item, loc = -1; clrscr (); printf ("\ nVoer het aantal elementen in:"); scanf ("% d", & n); printf ("Voer de cijfers in: \ n"); voor (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf ("\ nGeef het nummer op dat moet worden gezocht:"); scanf ("% d", & item); for (i = 0; i = 0) {printf ("\ n% d is te vinden in positie% d:", item, loc + 1); } else {printf ("\ n Item bestaat niet"); } getch (); }

Definitie van binair zoeken

Binair zoeken is een uiterst efficiënt algoritme. Deze zoektechniek kost minder tijd bij het doorzoeken van het gegeven item in minimaal mogelijke vergelijkingen. Om de binaire zoekactie uit te voeren, moeten we eerst de array-elementen sorteren.

De logica achter deze techniek wordt hieronder weergegeven:

Zoek eerst het middelste element van de array.
Het middelste element van de array wordt vergeleken met het element dat moet worden doorzocht.

Er kunnen zich drie gevallen voordoen:

Als het element het vereiste element is, is de zoekopdracht geslaagd.
Wanneer het element kleiner is dan het gewenste item, zoek dan alleen de eerste helft van de array.
Als het groter is dan het gewenste element, zoek dan in de tweede helft van de array.

Herhaal dezelfde stappen totdat een element wordt gevonden of uitput in het zoekgebied. In dit algoritme neemt elk zoekgebied af. Daarom is het aantal vergelijkingen maximaal log (N + 1). Het resultaat is een efficiënt algoritme in vergelijking met lineair zoeken, maar de array moet worden gesorteerd voordat de binaire zoekopdracht wordt uitgevoerd.

C Programma om een element met binaire zoektechniek te vinden.

 # include void main () {int i, bedelen, beëindigen, midden, n, zoeken, array [100]; printf ("Voer het aantal elementen in \ n"); scanf ( "% d", & n); printf ("Voer de% d-nummers in \ n", n); voor (i = 0; i <n; i ++) scanf ("% d", & array [i]); printf ("Voer het nummer in dat moet worden doorzocht \ n"); scanf ("% d", & zoeken); bedelen = 0; einde = n - 1; midden = (begin + einde) / 2; while (begin <= end) {if (array [midden] einde) printf ("Zoeken is mislukt!% d is niet aanwezig in de lijst. \ n", zoeken); getch (); }

Belangrijkste verschillen tussen lineair zoeken en binair zoeken

Lineair zoeken is iteratief van aard en gebruikt een sequentiële benadering. Aan de andere kant, binaire zoeken implementeert verdeel en heers aanpak.
De tijdcomplexiteit van lineair zoeken is O (N) terwijl binair zoeken O (log ₂ N) heeft.
De beste case-tijd in lineair zoeken is voor het eerste element, dwz O (1). Daartegenover staat bij binair zoeken het middelste element, dus O (1).
In de lineaire zoekopdracht is het grootste nadeel van het zoeken naar een element het N-vergelijkingsgetal. In tegenstelling hiermee is het een log ₂ N-vergelijkingsnummer voor binaire zoekbewerkingen.
Lineair zoeken kan zowel in een array als in een gelinkte lijst worden geïmplementeerd, terwijl binair zoeken niet rechtstreeks op de gekoppelde lijst kan worden geïmplementeerd.
Zoals we weten, vereist binair zoeken de gesorteerde array die reden is. Het vereist dat de verwerking op de juiste plaats wordt ingevoegd om een gesorteerde lijst te onderhouden. Integendeel, lineair zoeken vereist geen gesorteerde elementen, zodat elementen eenvoudig aan het einde van de lijst kunnen worden ingevoegd.
Lineair zoeken is gemakkelijk te gebruiken en er zijn geen bestelde elementen nodig. Aan de andere kant is het binaire zoekalgoritme echter lastig, en elementen worden noodzakelijkerwijs op volgorde gerangschikt.

Conclusie

Zowel lineaire als binaire zoekalgoritmen kunnen nuttig zijn, afhankelijk van de toepassing. Wanneer een array de gegevensstructuur is en elementen in gesorteerde volgorde zijn gerangschikt, heeft binaire zoekopdracht de voorkeur voor snel zoeken. Als de gekoppelde lijst de gegevensstructuur is, ongeacht hoe de elementen zijn gerangschikt, wordt lineair zoeken toegepast vanwege de niet-beschikbaarheid van directe implementatie van het binaire zoekalgoritme.

Het typische binaire zoekalgoritme kan niet worden gebruikt voor de gekoppelde lijst, omdat de gekoppelde lijst een dynamisch karakter heeft en het niet bekend is waar het middelste element feitelijk is toegewezen. Daarom is er een vereiste om de variatie van het binaire zoekalgoritme te ontwerpen dat ook op de gekoppelde lijst kan werken omdat het binaire zoeken sneller verloopt dan een lineaire zoekopdracht.