Binair zoeken versus lineair zoeken
Lineair zoeken, ook wel 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 die wordt gebruikt om een opgegeven waarde in een gesorteerde lijst te vinden. De binaire zoekmethode halveert het aantal gecontroleerde elementen (in elke iteratie), waardoor de tijd die nodig is om het gegeven item in de lijst te vinden, wordt verkort.
Wat is lineair zoeken?
Lineair zoeken is de eenvoudigste zoekmethode, die elk element in een lijst opeenvolgend controleert totdat het een gespecificeerd element vindt. De invoer voor de lineaire zoekmethode is een reeks (zoals een array, verzameling of een string) en het item dat moet worden doorzocht. De uitvoer is waar als het opgegeven item binnen de opgegeven reeks v alt of onwaar als het niet in de reeks staat. Aangezien deze methode elk item in de lijst controleert totdat het gespecificeerde item is gevonden, doorloopt het in het ergste geval alle elementen in de lijst voordat het het vereiste element vindt. De complexiteit van lineair zoeken is o(n). Daarom wordt het als te traag beschouwd 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 die wordt gebruikt om een gespecificeerd item in een gesorteerde lijst te vinden. Deze methode begint met het vergelijken van het gezochte element met de elementen in het midden van de lijst. Als de vergelijking bepa alt dat de twee elementen gelijk zijn, stopt de methode en wordt de positie van het element geretourneerd. 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 kleiner 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 staat, retourneert de methode een unieke waarde die dat aangeeft. Daarom halveert de binaire zoekmethode het aantal vergeleken elementen (in elke iteratie), afhankelijk van het resultaat van de vergelijking. Dientengevolge wordt binair zoeken 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 binair zoeken werkt op gesorteerde lijsten, kan voering zoeken ook werken op ongesorteerde lijsten. Het sorteren van een lijst heeft over het algemeen een gemiddelde casuscomplexiteit van n log n. lineair zoeken is eenvoudig en ongecompliceerd te implementeren dan de binaire zoekopdracht. Maar lineair zoeken is te traag om te worden gebruikt met grote lijsten vanwege de o(n) gemiddelde case-performance. Aan de andere kant wordt binair zoeken beschouwd als een efficiëntere methode die bij grote lijsten kan worden gebruikt. Maar het implementeren van binair zoeken kan behoorlijk lastig zijn en een onderzoek heeft aangetoond dat de juiste code voor binair zoeken in slechts vijf van de twintig boeken te vinden is.
