Binair zoeken versus lineair zoeken
Lineair zoeken, ook wel sequentieel zoeken 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, waarbij elk element in een lijst opeenvolgend wordt gecontroleerd totdat het een opgegeven 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 true als het opgegeven item binnen de opgegeven reeks valt of false als het niet in de reeks staat. Aangezien deze methode elk item in de lijst controleert totdat het opgegeven 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 bepaald 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 uit de vergelijking blijkt 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 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. Bijgevolg,binair zoeken wordt 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 liner zoeken ook werken op ongesorteerde lijsten. Het sorteren van een lijst heeft doorgaans een gemiddelde hoofdlettercomplexiteit van n log n. lineair zoeken is eenvoudig en ongecompliceerd te implementeren dan binair zoeken. Maar lineair zoeken is te traag om te worden gebruikt met grote lijsten vanwege de o (n) gemiddelde case-prestaties. Aan de andere kant wordt binair zoeken beschouwd als een efficiëntere methode die kan worden gebruikt met grote lijsten. Maar het implementeren van de binaire zoekopdracht kan behoorlijk lastig zijn en een studie heeft aangetoond dat de nauwkeurige code voor binaire zoekopdrachten slechts in vijf van de twintig boeken te vinden is.
