Verschil tussen binair zoeken en lineair zoeken

Binair zoeken versus lineair zoeken

Lineair zoeken, ook wel de sequentiële zoekopdracht genoemd, is het eenvoudigste zoekalgoritme. Het zoekt naar een opgegeven waarde in een lijst door elk element in de lijst te controleren. Binair zoeken is ook een methode om een ​​opgegeven waarde in een gesorteerde lijst te zoeken. Binaire zoekmethode halveert het aantal gecontroleerde elementen (in elke iteratie), waardoor de tijd die nodig is om het gegeven item in de lijst te lokaliseren korter wordt.

Wat is lineair zoeken?

Lineair zoeken is de eenvoudigste zoekmethode, die elk element in een lijst sequentieel controleert tot het een bepaald element vindt. De invoer voor de lineaire zoekmethode is een reeks (zoals een array, verzameling of een tekenreeks) en het item dat moet worden doorzocht. De uitvoer is waar als het opgegeven item binnen de opgegeven reeks valt of onwaar is als het niet in de reeks voorkomt. Aangezien deze methode elk item in de lijst controleert totdat het opgegeven item is gevonden, zal het in het ergste geval alle elementen in de lijst doorlopen voordat het het vereiste element vindt. De complexiteit van lineair zoeken is o (n). Daarom wordt het beschouwd als te traag om te worden gebruikt bij het zoeken naar elementen in grote lijsten. Maar dit is heel eenvoudig en gemakkelijker te implementeren.

Wat is binair zoeken?

Binair zoeken is ook een methode om een ​​bepaald item in een gesorteerde lijst te lokaliseren. Deze methode begint met het vergelijken van het gezochte element met de elementen in het midden van de lijst. Als de vergelijking bepaalt dat de twee elementen gelijk zijn, stopt de methode en retourneert de positie van het element. Als het gezochte element groter is dan het middelste element, wordt de methode opnieuw gestart met alleen de onderste helft van de gesorteerde lijst. Als het gezochte element minder is dan het middelste element, wordt de methode opnieuw gestart met alleen de bovenste helft van de gesorteerde lijst. Als het gezochte element niet in de lijst voorkomt, retourneert de methode een unieke waarde die dit aangeeft. Daarom halveert de binaire zoekmethode het aantal vergeleken elementen (in elke iteratie), afhankelijk van het resultaat van de vergelijking. Bijgevolg wordt binaire zoekactie uitgevoerd in logaritmische tijd, wat resulteert in o (log n) gemiddelde case-prestaties.

Wat is het verschil tussen binair zoeken en lineair zoeken?

Hoewel zowel lineair zoeken als binair zoeken zoekmethoden zijn, hebben ze verschillende verschillen. Terwijl het binaire zoeken werkt op gesorteerde lijsten, kan het zoeken naar voeringen ook op ongesorteerde lijsten werken. Het sorteren van een lijst heeft over het algemeen een gemiddelde complexiteit van de behuizing van n log n. lineair zoeken is eenvoudig en eenvoudig te implementeren dan het binaire zoeken. Maar lineair zoeken is te traag om met grote lijsten te gebruiken vanwege de o (n) gemiddelde case-prestaties. Aan de andere kant wordt binair zoeken beschouwd als een efficiëntere methode die met grote lijsten kan worden gebruikt. Maar het implementeren van de binaire zoekactie kan best lastig zijn en uit een onderzoek is gebleken dat de juiste code voor binaire zoekopdrachten slechts in vijf van de twintig boeken te vinden is.