Før vi forstår forskjellene mellom det lineære og binære søket, bør vi først kjenne til det lineære søket og det binære søket separat.
Hva er et lineært søk?
Et lineært søk er også kjent som et sekvensielt søk som ganske enkelt skanner hvert element om gangen. Anta at vi ønsker å søke etter et element i en matrise eller liste; vi beregner ganske enkelt lengden og hopper ikke på noen gjenstand.
La oss vurdere et enkelt eksempel.
Anta at vi har en matrise med 10 elementer som vist i figuren nedenfor:
Figuren ovenfor viser en rekke tegntyper med 10 verdier. Hvis vi vil søke 'E', begynner søket fra 0-enthelement og skanner hvert element til elementet, dvs. 'E' ikke er funnet. Vi kan ikke hoppe direkte fra 0thelement til 4thelement, dvs. hvert element skannes ett etter ett til elementet ikke blir funnet.
Kompleksiteten til lineært søk
Som lineært søk skanner hvert element ett etter ett til elementet ikke blir funnet. Hvis antallet elementer øker, økes også antallet elementer som skal skannes. Vi kan si at tiden det tar å søke i elementene er proporsjonal med antall elementer . Derfor er kompleksiteten i verste fall O(n)
Hva er et binært søk?
Et binært søk er et søk der midtelementet beregnes for å sjekke om det er mindre eller større enn elementet som skal søkes. Den største fordelen med å bruke binært søk er at det ikke skanner hvert element i listen. I stedet for å skanne hvert element, utfører den søket til halvdelen av listen. Så det binære søket tar mindre tid å søke i et element sammenlignet med et lineært søk.
Den ene forutsetning for binært søk er at en matrise skal være i sortert rekkefølge, mens det lineære søket fungerer på både sortert og usortert matrise. Den binære søkealgoritmen er basert på divide and conquer-teknikken, som betyr at den vil dele matrisen rekursivt.
Det er tre tilfeller brukt i det binære søket:
Tilfelle 1: data
Tilfelle 2: data>a[midt] så høyre=midt-1
Tilfelle 3: data = et [midt] // element er funnet
I tilfellet ovenfor, ' en ' er navnet på matrisen, midten er indeksen til elementet beregnet rekursivt, data er elementet som skal søkes, venstre angir det venstre elementet i matrisen og Ikke sant betegner elementet som forekommer på høyre side av matrisen.
La oss forstå hvordan binært søk fungerer gjennom et eksempel.
Anta at vi har en matrise på 10 størrelse som er indeksert fra 0 til 9 som vist i figuren nedenfor:
Vi ønsker å søke etter 70 element fra arrayet ovenfor.
Trinn 1: Først beregner vi midtelementet i en matrise. Vi vurderer to variabler, dvs. venstre og høyre. Til å begynne med venstre =0 og høyre=9 som vist i figuren nedenfor:
Den midterste elementverdien kan beregnes som:
Derfor er mid = 4 og a[mid] = 50. Elementet som skal søkes i er 70, så a[midt] er ikke lik data. Tilfellet 2 er tilfredsstilt, dvs. data>a[midt].
Steg 2: Som data>a[midt], så økes verdien av venstre med mid+1, dvs. venstre=midt+1. Verdien av mid er 4, så verdien av venstre blir 5. Nå har vi en undergruppe som vist i figuren nedenfor:
Nå igjen beregnes midtverdien ved å bruke formelen ovenfor, og verdien av mid blir 7. Nå kan midten representeres som:
I figuren ovenfor kan vi observere at a[mid]>data, så igjen vil verdien av mid bli beregnet i neste trinn.
Trinn 3: Som en[mid]>data reduseres verdien av rettighet med midten av 1. Verdien av mid er 7, så verdien av høyre blir 6. Matrisen kan representeres som:
Verdien av mid vil bli beregnet på nytt. Verdiene for venstre og høyre er henholdsvis 5 og 6. Derfor er verdien av mid 5. Nå kan midten representeres i en matrise som vist nedenfor:
I figuren ovenfor kan vi observere at en[mid]
Trinn 4: Som en [midt] Nå beregnes verdien av mid igjen ved å bruke formelen som vi allerede har diskutert. Verdiene til venstre og høyre er henholdsvis 6 og 6, så verdien av mid blir 6 som vist i figuren nedenfor: Vi kan observere i figuren ovenfor at a[mid]=data. Derfor er søket fullført, og elementet er funnet. Følgende er forskjellene mellom lineært søk og binært søk: Beskrivelse Lineært søk er et søk som finner et element i listen ved å søke i elementet sekvensielt til elementet er funnet i listen. På den annen side er et binært søk et søk som finner det midterste elementet i listen rekursivt til det midterste elementet matches med et søkt element. Fungerer av begge søkene Det lineære søket begynner å søke fra det første elementet og skanner ett element om gangen uten å hoppe til det neste elementet. På den annen side deler binært søk matrisen i to ved å beregne midtelementet til en matrise. Gjennomføring Det lineære søket kan implementeres på en hvilken som helst lineær datastruktur som vektor, enkeltlenket liste, dobbeltlenket liste. I motsetning til dette kan det binære søket implementeres på de datastrukturene med toveis traversering, det vil si forover og bakover. Kompleksitet Det lineære søket er enkelt å bruke, eller vi kan si at det er mindre komplekst da elementene for et lineært søk kan ordnes i hvilken som helst rekkefølge, mens i et binært søk må elementene ordnes i en bestemt rekkefølge. Sorterte elementer Elementene for et lineært søk kan ordnes i tilfeldig rekkefølge. Det er ikke obligatorisk ved lineært søk at elementene er ordnet i en sortert rekkefølge. På den annen side, i et binært søk, må elementene ordnes i sortert rekkefølge. Det kan ordnes enten i økende eller i synkende rekkefølge, og følgelig vil algoritmen endres. Siden binært søk bruker en sortert matrise, er det nødvendig å sette inn elementet på riktig sted. Derimot trenger ikke det lineære søket en sortert matrise, slik at det nye elementet enkelt kan settes inn på slutten av matrisen. Nærme seg Det lineære søket bruker en iterativ tilnærming for å finne elementet, så det er også kjent som en sekvensiell tilnærming. Derimot beregner det binære søket det midterste elementet i matrisen, så det bruker del og hersk-tilnærmingen. Datasett Lineært søk er ikke egnet for det store datasettet. Hvis vi ønsker å søke i elementet, som er det siste elementet i matrisen, vil et lineært søk begynne å søke fra det første elementet og fortsette til det siste elementet, så tiden det tar å søke i elementet vil være stor. På den annen side er binært søk egnet for et stort datasett da det tar kortere tid. Hastighet Hvis datasettet er stort i lineært søk, vil beregningskostnaden være høy, og hastigheten blir langsom. Hvis datasettet er stort i binært søk, vil beregningskostnaden være mindre sammenlignet med et lineært søk, og hastigheten blir rask. Dimensjoner Lineært søk kan brukes på både en- og flerdimensjonal matrise, mens det binære søket bare kan implementeres på den endimensjonale matrisen. Effektivitet Lineært søk er mindre effektivt når vi vurderer de store datasettene. Binært søk er mer effektivt enn lineært søk når det gjelder store datasett. La oss se på forskjellene i en tabellform. 
Forskjeller mellom lineært søk og binært søk
upcasting
Grunnlag for sammenligning Lineært søk Binært søk Definisjon Det lineære søket begynner å søke fra det første elementet og sammenligner hvert element med et søkt element til elementet ikke blir funnet. Den finner posisjonen til det søkte elementet ved å finne det midterste elementet i matrisen. Sorterte data I et lineært søk trenger ikke elementene å ordnes i sortert rekkefølge. Forutsetningen for det binære søket er at elementene må ordnes i en sortert rekkefølge. Gjennomføring Det lineære søket kan implementeres på en hvilken som helst lineær datastruktur som en matrise, koblet liste, etc. Implementeringen av binært søk er begrenset ettersom det bare kan implementeres på de datastrukturene som har toveis traversering. Nærme seg Den er basert på den sekvensielle tilnærmingen. Den er basert på skille og hersk-tilnærmingen. Størrelse Det er å foretrekke for små datasett. Det er å foretrekke for store datasett. Effektivitet Det er mindre effektivt når det gjelder store datasett. Det er mer effektivt når det gjelder store datasett. I verste fall I et lineært søk er det verste tilfellet for å finne elementet O(n). I et binært søk er det verste scenarioet for å finne elementet O(log2n). Best-case scenario I et lineært søk er det beste scenarioet for å finne det første elementet i listen O(1). I et binært søk er det beste scenarioet for å finne det første elementet i listen O(1). Dimensjonssett Det kan implementeres på både en enkelt og flerdimensjonal array. Det kan bare implementeres på en flerdimensjonal matrise.