Før vi forstår forskellene mellem den lineære og binære søgning, bør vi først kende den lineære søgning og den binære søgning separat.
Hvad er en lineær søgning?
En lineær søgning er også kendt som en sekventiel søgning, der blot scanner hvert element ad gangen. Antag, at vi vil søge efter et element i en matrix eller liste; vi beregner simpelthen dens længde og hopper ikke på nogen genstand.
Lad os overveje et simpelt eksempel.
Antag, at vi har en matrix med 10 elementer som vist i nedenstående figur:
Ovenstående figur viser et array af tegntyper med 10 værdier. Hvis vi ønsker at søge 'E', så begynder søgningen fra 0thelement og scanner hvert element, indtil elementet, dvs. 'E' ikke findes. Vi kan ikke springe direkte fra 0thelement til 4thelement, dvs. hvert element scannes et efter et, indtil elementet ikke findes.
Kompleksiteten af lineær søgning
Som lineær søgning scanner hvert element et efter et, indtil elementet ikke findes. Hvis antallet af elementer stiger, øges antallet af elementer, der skal scannes, også. Vi kan sige, at tid det tager at søge i elementerne er proportional med antallet af elementer . Derfor er den værste kompleksitet O(n)
Hvad er en binær søgning?
En binær søgning er en søgning, hvor det midterste element beregnes for at kontrollere, om det er mindre eller større end det element, der skal søges i. Den største fordel ved at bruge binær søgning er, at den ikke scanner hvert element i listen. I stedet for at scanne hvert element, udfører den søgningen til halvdelen af listen. Så den binære søgning tager mindre tid at søge efter et element sammenlignet med en lineær søgning.
Den ene forudsætning for binær søgning er, at et array skal være i sorteret rækkefølge, hvorimod den lineære søgning fungerer på både sorteret og usorteret array. Den binære søgealgoritme er baseret på divide and conquer-teknikken, hvilket betyder, at den vil opdele arrayet rekursivt.
Der er tre tilfælde brugt i den binære søgning:
Case 1: data
Tilfælde 2: data>a[mid] derefter højre=midt-1
Tilfælde 3: data = a[mid] // element er fundet
I ovenstående tilfælde, -en ' er navnet på arrayet, midt er indekset for elementet beregnet rekursivt, data er det element, der skal søges i, venstre angiver det venstre element i arrayet og højre angiver det element, der forekommer på højre side af arrayet.
Lad os forstå, hvordan binær søgning fungerer gennem et eksempel.
Antag, at vi har en matrix på 10 størrelse, som er indekseret fra 0 til 9 som vist i nedenstående figur:
Vi ønsker at søge efter 70 element fra ovenstående array.
Trin 1: Først beregner vi det midterste element i en matrix. Vi betragter to variable, dvs. venstre og højre. Til at begynde med venstre =0 og højre=9 som vist i nedenstående figur:
Den midterste elementværdi kan beregnes som:
Derfor er mid = 4 og a[mid] = 50. Elementet, der skal søges i, er 70, så a[mid] er ikke lig med data. Tilfældet 2 er opfyldt, dvs. data>a[mid].
Trin 2: Som data>a[midt], så værdien af venstre øges med mid+1, dvs. venstre=midt+1. Værdien af mid er 4, så værdien af venstre bliver 5. Nu har vi fået en subarray som vist i nedenstående figur:
Nu igen beregnes mellemværdien ved at bruge ovenstående formel, og værdien af mid bliver 7. Nu kan midten repræsenteres som:
I ovenstående figur kan vi observere, at a[mid]>data, så igen vil værdien af mid blive beregnet i næste trin.
Trin 3: Som en[mid]>data er værdien af højre formindsket med mid-1. Værdien af mid er 7, så værdien af højre bliver 6. Arrayet kan repræsenteres som:
Værdien af mid vil blive beregnet igen. Værdierne for venstre og højre er henholdsvis 5 og 6. Derfor er værdien af mid 5. Nu kan midten repræsenteres i en matrix som vist nedenfor:
I ovenstående figur kan vi observere, at en[mid]
Trin 4: Som [midt] Nu beregnes værdien af mid igen ved at bruge formlen, som vi allerede har diskuteret. Værdierne for venstre og højre er henholdsvis 6 og 6, så værdien af mid bliver 6 som vist i nedenstående figur: Vi kan observere i ovenstående figur, at a[mid]=data. Derfor er søgningen afsluttet, og elementet er fundet med succes. Følgende er forskellene mellem lineær søgning og binær søgning: Beskrivelse Lineær søgning er en søgning, der finder et element i listen ved at søge elementet sekventielt, indtil elementet er fundet i listen. På den anden side er en binær søgning en søgning, der finder det midterste element i listen rekursivt, indtil det midterste element matches med et søgt element. Fungerer af begge søgninger Den lineære søgning starter søgningen fra det første element og scanner et element ad gangen uden at hoppe til det næste element. På den anden side deler binær søgning arrayet i halvdelen ved at beregne et arrays midterste element. Implementering Den lineære søgning kan implementeres på enhver lineær datastruktur, såsom vektor, enkeltforbundet liste, dobbeltlænket liste. I modsætning hertil kan den binære søgning implementeres på disse datastrukturer med to-vejs traversal, dvs. fremadgående og bagudgående traversering. Kompleksitet Den lineære søgning er nem at bruge, eller vi kan sige, at den er mindre kompleks, da elementerne til en lineær søgning kan arrangeres i en hvilken som helst rækkefølge, hvorimod elementerne i en binær søgning skal arrangeres i en bestemt rækkefølge. Sorterede elementer Elementerne til en lineær søgning kan arrangeres i tilfældig rækkefølge. Det er ikke obligatorisk ved lineær søgning, at elementerne er ordnet i en sorteret rækkefølge. På den anden side skal elementerne i en binær søgning arrangeres i sorteret rækkefølge. Det kan arrangeres enten i stigende eller faldende rækkefølge, og algoritmen vil derfor blive ændret. Da binær søgning bruger et sorteret array, er det nødvendigt at indsætte elementet på det rigtige sted. I modsætning hertil behøver den lineære søgning ikke et sorteret array, så det nye element nemt kan indsættes i slutningen af arrayet. Nærme sig Den lineære søgning bruger en iterativ tilgang til at finde elementet, så det er også kendt som en sekventiel tilgang. I modsætning hertil beregner den binære søgning det midterste element i arrayet, så den bruger opdel og hersk tilgangen. Datasæt Lineær søgning er ikke egnet til det store datasæt. Hvis vi vil søge i elementet, som er det sidste element i arrayet, vil en lineær søgning begynde at søge fra det første element og fortsætte til det sidste element, så den tid, det tager at søge i elementet, ville være stor. På den anden side er binær søgning velegnet til et stort datasæt, da det tager kortere tid. Fart Hvis datasættet er stort i lineær søgning, ville beregningsomkostningerne være høje, og hastigheden bliver langsom. Hvis datasættet er stort i binær søgning, ville beregningsomkostningerne være mindre sammenlignet med en lineær søgning, og hastigheden bliver hurtig. Dimensioner Lineær søgning kan bruges på både enkelt- og multidimensionelt array, hvorimod den binære søgning kun kan implementeres på den en-dimensionelle array. Effektivitet Lineær søgning er mindre effektiv, når vi betragter de store datasæt. Binær søgning er mere effektiv end den lineære søgning i tilfælde af store datasæt. Lad os se på forskellene i en tabelform. 
Forskelle mellem lineær søgning og binær søgning
upcasting
Sammenligningsgrundlag Lineær søgning Binær søgning Definition Den lineære søgning starter søgningen fra det første element og sammenligner hvert element med et søgt element, indtil elementet ikke er fundet. Den finder positionen af det søgte element ved at finde det midterste element i arrayet. Sorterede data I en lineær søgning behøver elementerne ikke at være ordnet i sorteret rækkefølge. Forudsætningen for den binære søgning er, at elementerne skal arrangeres i en sorteret rækkefølge. Implementering Den lineære søgning kan implementeres på en hvilken som helst lineær datastruktur, såsom en matrix, linket liste osv. Implementeringen af binær søgning er begrænset, da den kun kan implementeres på de datastrukturer, der har to-vejs traversering. Nærme sig Det er baseret på den sekventielle tilgang. Det er baseret på opdel og hersk tilgangen. Størrelse Det er at foretrække for små datasæt. Det er at foretrække for de store datasæt. Effektivitet Det er mindre effektivt i tilfælde af store datasæt. Det er mere effektivt i tilfælde af store datasæt. Værste tilfælde I en lineær søgning er det værst tænkelige scenarie for at finde elementet O(n). I en binær søgning er det værste tilfælde for at finde elementet O(log2n). Bedste scenario I en lineær søgning er det bedste scenario for at finde det første element på listen O(1). I en binær søgning er det bedste scenario for at finde det første element på listen O(1). Dimensionelt array Det kan implementeres på både et enkelt og multidimensionelt array. Det kan kun implementeres på et multidimensionelt array.