Innan vi förstår skillnaderna mellan den linjära och binära sökningen bör vi först känna till den linjära sökningen och den binära sökningen separat.
Vad är en linjär sökning?
En linjär sökning är också känd som en sekventiell sökning som helt enkelt skannar varje element åt gången. Anta att vi vill söka efter ett element i en array eller lista; vi beräknar helt enkelt dess längd och hoppar inte på något föremål.
Låt oss överväga ett enkelt exempel.
Anta att vi har en array med 10 element som visas i bilden nedan:
Ovanstående figur visar en array av teckentyp med 10 värden. Om vi vill söka efter 'E' börjar sökningen från nollanthelement och skannar varje element tills elementet, dvs 'E' inte hittas. Vi kan inte hoppa direkt från nollanthelement till 4:anthelement, dvs varje element skannas ett efter ett tills elementet inte hittas.
Komplexiteten i linjär sökning
Som linjär sökning skannar varje element ett efter ett tills elementet inte hittas. Om antalet element ökar, ökas också antalet element som ska skannas. Vi kan säga att tiden det tar att söka i elementen är proportionell mot antalet element . Därför är den värsta komplexiteten O(n)
Vad är en binär sökning?
En binär sökning är en sökning där mittelementet beräknas för att kontrollera om det är mindre eller större än elementet som ska sökas. Den största fördelen med att använda binär sökning är att den inte skannar varje element i listan. Istället för att skanna varje element, utför den sökningen till hälften av listan. Så den binära sökningen tar mindre tid att söka efter ett element jämfört med en linjär sökning.
Den rätta förutsättning för binär sökning är att en matris ska vara i sorterad ordning, medan den linjära sökningen fungerar på både sorterad och osorterad matris. Den binära sökalgoritmen är baserad på divide and conquer-tekniken, vilket innebär att den kommer att dela upp arrayen rekursivt.
Det finns tre fall som används i den binära sökningen:
Fall 1: data
Fall 2: data>a[mid] sedan höger=mid-1
Fall 3: data = a[mid] // element hittas
I ovanstående fall, ' a ' är namnet på arrayen, mitten är indexet för elementet beräknat rekursivt, data är elementet som ska sökas, vänster betecknar det vänstra elementet i arrayen och höger betecknar elementet som förekommer på höger sida av arrayen.
Låt oss förstå hur binär sökning fungerar genom ett exempel.
Anta att vi har en array med storleken 10 som är indexerad från 0 till 9 som visas i bilden nedan:
Vi vill söka efter 70 element från ovanstående array.
Steg 1: Först beräknar vi mittelementet i en array. Vi betraktar två variabler, det vill säga vänster och höger. Inledningsvis vänster =0 och höger=9 som visas i bilden nedan:
Det mellersta elementvärdet kan beräknas som:
Därför är mid = 4 och a[mid] = 50. Elementet som ska sökas är 70, så a[mid] är inte lika med data. Fall 2 är uppfyllt, d.v.s. data>a[mid].
Steg 2: Som data>a[mid], så ökas värdet på vänster med mitt+1, dvs vänster=mid+1. Värdet på mid är 4, så värdet på vänster blir 5. Nu har vi en subarray som visas i bilden nedan:
Nu igen beräknas mittvärdet genom att använda formeln ovan, och värdet på mitten blir 7. Nu kan mitten representeras som:
I figuren ovan kan vi observera att a[mid]>data, så återigen kommer värdet på mid att beräknas i nästa steg.
Steg 3: Som en[mid]>data minskas värdet av rätt med mitten av 1. Värdet på mid är 7, så värdet på höger blir 6. Arrayen kan representeras som:
Värdet på mid kommer att beräknas igen. Värdena för vänster och höger är 5 respektive 6. Därför är värdet på mid 5. Nu kan mitten representeras i en array som visas nedan:
I figuren ovan kan vi observera att en[mid]
Steg 4: Som en[mitt] Nu beräknas värdet av mid igen med hjälp av formeln som vi redan har diskuterat. Värdena för vänster och höger är 6 respektive 6, så värdet på mid blir 6 som visas i bilden nedan: Vi kan observera i figuren ovan att a[mid]=data. Därför är sökningen klar och elementet hittas framgångsrikt. Följande är skillnaderna mellan linjär sökning och binär sökning: Beskrivning Linjär sökning är en sökning som hittar ett element i listan genom att söka elementet sekventiellt tills elementet hittas i listan. Å andra sidan är en binär sökning en sökning som hittar mittelementet i listan rekursivt tills mittelementet matchas med ett sökt element. Fungerar av båda sökningarna Den linjära sökningen börjar söka från det första elementet och skannar ett element i taget utan att hoppa till nästa element. Å andra sidan delar binär sökning arrayen i hälften genom att beräkna en arrays mittelement. Genomförande Den linjära sökningen kan implementeras på vilken linjär datastruktur som helst, såsom vektor, enkellänkad lista, dubbellänkad lista. Däremot kan den binära sökningen implementeras på dessa datastrukturer med tvåvägs-traversering, dvs framåt och bakåt. Komplexitet Den linjära sökningen är lätt att använda, eller så kan vi säga att den är mindre komplex eftersom elementen för en linjär sökning kan ordnas i valfri ordning, medan i en binär sökning måste elementen ordnas i en viss ordning. Sorterade element Elementen för en linjär sökning kan ordnas i slumpmässig ordning. Det är inte obligatoriskt vid linjär sökning att elementen är ordnade i en sorterad ordning. Å andra sidan, i en binär sökning måste elementen ordnas i sorterad ordning. Den kan ordnas antingen i ökande eller minskande ordning, och följaktligen kommer algoritmen att ändras. Eftersom binär sökning använder en sorterad array är det nödvändigt att infoga elementet på rätt plats. Däremot behöver den linjära sökningen inte en sorterad array, så att det nya elementet enkelt kan infogas i slutet av arrayen. Närma sig Den linjära sökningen använder ett iterativt tillvägagångssätt för att hitta elementet, så det är också känt som ett sekventiellt tillvägagångssätt. Däremot beräknar den binära sökningen mittelementet i arrayen, så den använder dividera och erövra-metoden. Datauppsättning Linjär sökning är inte lämplig för den stora datamängden. Om vi vill söka i elementet, som är det sista elementet i arrayen, kommer en linjär sökning att börja söka från det första elementet och fortsätta till det sista elementet, så tiden det tar att söka i elementet skulle vara lång. Å andra sidan är binär sökning lämplig för en stor datamängd eftersom det tar kortare tid. Fart Om datamängden är stor vid linjär sökning skulle beräkningskostnaden bli hög och hastigheten blir långsam. Om datamängden är stor i binär sökning, skulle beräkningskostnaden vara mindre jämfört med en linjär sökning, och hastigheten blir snabb. Mått Linjär sökning kan användas på både enkel- och flerdimensionell array, medan den binära sökningen endast kan implementeras på den endimensionella arrayen. Effektivitet Linjär sökning är mindre effektiv när vi tar hänsyn till de stora datamängderna. Binär sökning är effektivare än linjär sökning när det gäller stora datamängder. Låt oss titta på skillnaderna i en tabellform. 
Skillnader mellan linjär sökning och binär sökning
uml diagram java
Jämförelsegrund Linjär sökning Binär sökning Definition Den linjära sökningen börjar söka från det första elementet och jämför varje element med ett sökt element tills elementet inte hittas. Den hittar positionen för det sökta elementet genom att hitta mittelementet i arrayen. Sorterade data I en linjär sökning behöver elementen inte ordnas i sorterad ordning. Förutsättningen för den binära sökningen är att elementen måste ordnas i en sorterad ordning. Genomförande Den linjära sökningen kan implementeras på vilken linjär datastruktur som helst som en array, länkad lista, etc. Implementeringen av binär sökning är begränsad eftersom den endast kan implementeras på de datastrukturer som har tvåvägs-traversering. Närma sig Den är baserad på den sekventiella metoden. Den är baserad på dela och härska-metoden. Storlek Det är att föredra för små datamängder. Det är att föredra för stora datamängder. Effektivitet Det är mindre effektivt när det gäller stora datamängder. Det är mer effektivt när det gäller stora datamängder. I värsta fall I en linjär sökning är det värsta scenariot för att hitta elementet O(n). I en binär sökning är det värsta scenariot för att hitta elementet O(log2n). Bästa scenario I en linjär sökning är det bästa scenariot för att hitta det första elementet i listan O(1). I en binär sökning är det bästa scenariot för att hitta det första elementet i listan O(1). Dimensionell array Det kan implementeras på både en enkel och flerdimensionell array. Det kan endast implementeras på en flerdimensionell array.