Voordat we de verschillen tussen lineair en binair zoeken begrijpen, moeten we eerst het lineaire zoeken en het binaire zoeken afzonderlijk kennen.
Wat is een lineaire zoekopdracht?
Een lineaire zoekopdracht wordt ook wel een sequentiële zoekopdracht genoemd, waarbij eenvoudigweg elk element tegelijk wordt gescand. Stel dat we een element in een array of lijst willen doorzoeken; we berekenen eenvoudigweg de lengte ervan en springen op geen enkel item.
Laten we een eenvoudig voorbeeld bekijken.
Stel dat we een array van 10 elementen hebben, zoals weergegeven in de onderstaande afbeelding:
De bovenstaande afbeelding toont een reeks tekentypen met 10 waarden. Als we 'E' willen zoeken, begint het zoeken vanaf de 0eelement en scant elk element totdat het element, d.w.z. 'E', niet is gevonden. We kunnen niet rechtstreeks van de 0 springeneonderdeel van de 4eelement, d.w.z. elk element wordt één voor één gescand totdat het element niet wordt gevonden.
Complexiteit van lineair zoeken
Terwijl lineair zoeken elk element één voor één scant totdat het element niet wordt gevonden. Als het aantal elementen toeneemt, wordt ook het aantal te scannen elementen vergroot. Wij kunnen zeggen dat de De tijd die nodig is om de elementen te doorzoeken is evenredig met het aantal elementen . Daarom is de worst-case complexiteit O(n)
Wat is een binaire zoekopdracht?
Een binaire zoekopdracht is een zoekopdracht waarbij het middelste element wordt berekend om te controleren of dit kleiner of groter is dan het element dat moet worden doorzocht. Het belangrijkste voordeel van het gebruik van binair zoeken is dat niet elk element in de lijst wordt gescand. In plaats van elk element te scannen, wordt er gezocht naar de helft van de lijst. De binaire zoekopdracht kost dus minder tijd om een element te doorzoeken in vergelijking met een lineaire zoekopdracht.
Degene voorwaarde voor binair zoeken is dat een array in gesorteerde volgorde moet staan, terwijl de lineaire zoekactie zowel op gesorteerde als op ongesorteerde arrays werkt. Het binaire zoekalgoritme is gebaseerd op de verdeel-en-heers-techniek, wat betekent dat het de array recursief verdeelt.
Er worden drie gevallen gebruikt bij de binaire zoekopdracht:
Geval 1: gegevens
Geval 2: data>a[mid] en dan rechts=mid-1
Geval 3: data = a[mid] // element gevonden
In het bovenstaande geval ' A ' is de naam van de array, midden is de index van het element recursief berekend, gegevens is het element dat moet worden doorzocht, links geeft het linkerelement van de array aan en rechts geeft het element aan dat aan de rechterkant van de array voorkomt.
Laten we de werking van binair zoeken begrijpen aan de hand van een voorbeeld.
Stel dat we een array van 10-grootte hebben die is geïndexeerd van 0 tot 9, zoals weergegeven in de onderstaande afbeelding:
We willen zoeken naar 70 elementen uit de bovenstaande array.
Stap 1: Eerst berekenen we het middelste element van een array. We beschouwen twee variabelen, namelijk links en rechts. Aanvankelijk is links =0 en rechts=9, zoals weergegeven in de onderstaande afbeelding:
De middelste elementwaarde kan als volgt worden berekend:
Daarom mid = 4 en a[mid] = 50. Het te doorzoeken element is 70, dus a[mid] is niet gelijk aan data. Aan geval 2 is voldaan, d.w.z. data>a[mid].
Stap 2: Als data>a[mid], wordt de waarde van left verhoogd met mid+1, d.w.z. left=mid+1. De waarde van mid is 4, dus de waarde van left wordt 5. Nu hebben we een subarray zoals weergegeven in de onderstaande afbeelding:
Ook nu wordt de middenwaarde berekend met behulp van de bovenstaande formule, en de waarde van midden wordt 7. Nu kan het midden worden weergegeven als:
In de bovenstaande figuur kunnen we zien dat a[mid]>data, dus nogmaals, de waarde van mid zal in de volgende stap worden berekend.
Stap 3: Als [mid]>gegevens wordt de waarde van rechts met midden 1 verlaagd. De waarde van mid is 7, dus de waarde van rechts wordt 6. De array kan worden weergegeven als:
De waarde van mid wordt opnieuw berekend. De waarden van links en rechts zijn respectievelijk 5 en 6. Daarom is de waarde van mid 5. Nu kan het mid worden weergegeven in een array, zoals hieronder weergegeven:
In de bovenstaande figuur kunnen we zien dat a[mid]
Stap 4: Als [midden] Nu wordt de waarde van mid opnieuw berekend met behulp van de formule die we al hebben besproken. De waarden van links en rechts zijn respectievelijk 6 en 6, dus de waarde van midden wordt 6, zoals weergegeven in de onderstaande afbeelding: We kunnen in de bovenstaande figuur zien dat a[mid]=data. Daarom is de zoekopdracht voltooid en is het element met succes gevonden. Hieronder volgen de verschillen tussen lineair zoeken en binair zoeken: Beschrijving Lineair zoeken is een zoekopdracht waarbij een element in de lijst wordt gevonden door het element opeenvolgend te doorzoeken totdat het element in de lijst wordt gevonden. Aan de andere kant is een binaire zoekopdracht een zoekopdracht waarbij het middelste element in de lijst recursief wordt gevonden totdat het middelste element wordt gekoppeld aan een gezocht element. Werking van beide zoekopdrachten De lineaire zoekactie begint met zoeken vanaf het eerste element en scant element voor element zonder naar het volgende element te springen. Aan de andere kant verdeelt binair zoeken de array in tweeën door het middelste element van een array te berekenen. Implementatie Het lineaire zoeken kan worden geïmplementeerd op elke lineaire datastructuur, zoals vector, enkelvoudig gekoppelde lijst, dubbel gekoppelde lijst. Daarentegen kan het binaire zoeken worden geïmplementeerd op die datastructuren met tweerichtingsverkeer, dat wil zeggen voorwaartse en achterwaartse verplaatsing. Complexiteit Lineair zoeken is gemakkelijk te gebruiken, of we kunnen zeggen dat het minder complex is, omdat de elementen voor lineair zoeken in elke volgorde kunnen worden gerangschikt, terwijl bij binair zoeken de elementen in een bepaalde volgorde moeten worden gerangschikt. Gesorteerde elementen De elementen voor een lineaire zoekopdracht kunnen in willekeurige volgorde worden gerangschikt. Bij lineair zoeken is het niet verplicht dat de elementen in een gesorteerde volgorde worden gerangschikt. Aan de andere kant moeten de elementen bij een binaire zoekopdracht in gesorteerde volgorde worden gerangschikt. Het kan in toenemende of in afnemende volgorde worden gerangschikt, en dienovereenkomstig zal het algoritme worden gewijzigd. Omdat binair zoeken een gesorteerde array gebruikt, is het noodzakelijk om het element op de juiste plaats in te voegen. Bij lineair zoeken is daarentegen geen gesorteerde array nodig, zodat het nieuwe element eenvoudig aan het einde van de array kan worden ingevoegd. Benadering Bij het lineair zoeken wordt gebruik gemaakt van een iteratieve benadering om het element te vinden, daarom wordt het ook wel een sequentiële benadering genoemd. De binaire zoekopdracht berekent daarentegen het middelste element van de array en gebruikt daarom de verdeel-en-heers-aanpak. Gegevensset Lineair zoeken is niet geschikt voor de grote dataset. Als we het element willen doorzoeken, wat het laatste element van de array is, zal een lineaire zoekopdracht beginnen met zoeken vanaf het eerste element en doorgaan tot aan het laatste element, dus de tijd die nodig is om het element te doorzoeken zou groot zijn. Aan de andere kant is binair zoeken geschikt voor een grote dataset, omdat het minder tijd kost. Snelheid Als de dataset bij lineair zoeken groot is, zouden de rekenkosten hoog zijn en zou de snelheid laag worden. Als de dataset bij binair zoeken groot is, zijn de rekenkosten lager in vergelijking met bij lineair zoeken, en wordt de snelheid hoog. Dimensies Lineair zoeken kan worden gebruikt op zowel enkelvoudige als multidimensionale arrays, terwijl binair zoeken alleen kan worden geïmplementeerd op de eendimensionale array. Efficiëntie Lineair zoeken is minder efficiënt als we rekening houden met grote datasets. Binair zoeken is efficiënter dan lineair zoeken in het geval van grote datasets. Laten we de verschillen in tabelvorm bekijken. 
Verschillen tussen lineair zoeken en binair zoeken
.is gelijk aan Java
Basis van vergelijking Lineair zoeken Binaire zoekopdracht Definitie De lineaire zoekopdracht begint met zoeken vanaf het eerste element en vergelijkt elk element met een gezocht element totdat het element niet wordt gevonden. Het vindt de positie van het gezochte element door het middelste element van de array te vinden. Gesorteerde gegevens Bij een lineaire zoekopdracht hoeven de elementen niet in gesorteerde volgorde te worden gerangschikt. De voorwaarde voor het binair zoeken is dat de elementen in een gesorteerde volgorde moeten worden gerangschikt. Implementatie De lineaire zoekopdracht kan worden geïmplementeerd op elke lineaire datastructuur, zoals een array, gekoppelde lijst, enz. De implementatie van binair zoeken is beperkt omdat het alleen kan worden geïmplementeerd op datastructuren die tweerichtingsverkeer hebben. Benadering Het is gebaseerd op de sequentiële aanpak. Het is gebaseerd op de verdeel en heers-aanpak. Maat Het verdient de voorkeur voor kleine datasets. Het verdient de voorkeur voor grote datasets. Efficiëntie Het is minder efficiënt in het geval van grote datasets. Het is efficiënter in het geval van grote datasets. In het slechtste geval Bij een lineaire zoekopdracht is het worstcasescenario voor het vinden van het element O(n). Bij een binaire zoekopdracht is het worstcasescenario voor het vinden van het element O(log2N). In het gunstigste geval Bij een lineaire zoekopdracht is O(1) het beste scenario voor het vinden van het eerste element in de lijst. Bij een binaire zoekopdracht is O(1) het beste scenario voor het vinden van het eerste element in de lijst. Dimensionale array Het kan worden geïmplementeerd op zowel een enkele als een multidimensionale array. Het kan alleen worden geïmplementeerd op een multidimensionale array.