introduction searching algorithms c
En översikt över sökning av algoritmer i C ++.
Vi fortsätter att leta efter något eller det andra i vår vardag. Precis som vår vardag, som programvaruprofessionell, måste vi söka efter information på vår dator. Informationssökning bör ske snabbt eftersom vi inte har råd att slösa bort mycket tid på att leta efter information.
Därför behöver vi några effektiva söktekniker eller algoritmer som kan söka i en viss information på kort tid och ge till användaren så att användaren kan gå vidare med de andra uppgifterna.
=> Besök här för en fullständig lista över C ++ -studier.
Vad du kommer att lära dig:
Söktekniker
Vi har två huvudsakliga söktekniker som oftast används för att söka efter information.
Dessa inkluderar:
- Linjär sökning
- Binär sökning
I denna handledning kommer vi att undersöka båda dessa söktekniker i detalj.
Linjär sökning
Detta är den mest grundläggande söktekniken och är lättare att implementera också. I en linjär sökning jämförs nyckeln som ska sökas linjärt med varje element i datainsamlingen. Denna teknik fungerar effektivt på linjära datastrukturer.
Låt oss överväga följande array.
Ovan finns matrisen med sju element. Om vi vill söka på tangenten = 23, börja med 0thelement kommer nyckelvärdet att jämföras med varje element. När nyckelelementet matchar elementet i matrisen kommer den specifika platsen att returneras. I det här fallet returneras 4 eftersom nyckelvärdet matchar värdet på den platsen.
Vi har implementerat en linjär sökning med C ++ och Java-språk nedan.
C ++ Implementering
#include #include using namespace std; int main() { int myarray(10) = {21,43,23,54,75,13,5,8,25,10}; int key,loc; cout<<'The input array is'<key; for (int i = 0; i<10; i++) { if(myarray(i) == key) { loc = i+1; break; } else loc = 0; } if(loc != 0) { cout<<'Key found at position '< Produktion:
pl / sql utvecklare intervju frågor
Inmatningsmatrisen är
21 43 23 54 75 13 5 8 25 10
Ange nyckeln som ska sökas: 3
Det gick inte att hitta den angivna nyckeln i matrisen
Inmatningsmatrisen är
21 43 23 54 75 13 5 8 25 10
Ange nyckeln som ska sökas: 75
Nyckel som finns vid position 5 i matrisen
Java-implementering
import java.util.*; import java.lang.*; import java.io.*; public class Main { public static void main(String() args) { int() myarray = {21,43,23,54,75,13,5,8,25,10}; int key,location=0; Scanner sc = new Scanner(System.in); System.out.println('The input array is'); for(int i=0;i<10;i++){ System.out.print(myarray(i)+' '); } System.out.println('
'); System.out.println('Enter key'); key = sc.nextInt(); for(int i = 0; i<10; i++) { if(myarray(i)==key) { location = i+1; break; } else location = 0; } if(location != 0) { System.out.println('key found at location ' + location); } else System.out.println('Key not found'); } } Produktion:
Inmatningsmatrisen är
21 43 23 54 75 13 5 8 25 10
Enter-tangent
2. 3
nyckel som finns på plats 3
Linjär sökning kan utföras på vilken linjär datastruktur som helst med sorterade eller osorterade element. Men det tar längre tid om det finns för många element och om nyckelelementet är mot slutet eftersom varje element jämförs med nyckelvärdet.
Binär sökning
Binär sökning är en teknik som använder 'dela och erövra' -teknik för att söka efter en nyckel. Det fungerar på en sorterad linjär lista över element. Den sorterade listan är grundkravet för att en binär sökning ska fungera.
I den binära sökmetoden delas listan upprepade gånger i halva och nyckelelementet söks i båda halvorna av listan tills nyckeln hittas.
Till exempel,låt oss ta följande sorterade matris med 10 element.
vad är den bästa programvaran för uppgiftshantering
Låt oss säga att nyckeln = 21 ska sökas i matrisen.
Låt oss beräkna matrisens mittposition.
Mitt = 0 + 9/2 = 4
Till exempel,låt oss ta följande sorterade matris med 10 element.
Nyckel = 21
Först kommer vi att jämföra nyckelvärdet med (mitt) -elementet. Vi finner att elementvärdet vid mitten = 21.
Således hittar vi den nyckeln = (mitt). Därför finns nyckeln.
nyckel = 25
Vi jämför först nyckelvärdet med mitten. Så (21<25), we will directly search for the key in the upper half of the array.
Nu åter hittar vi mitten för den övre halvan av matrisen.
Mitt = 4 + 9/2 = 6
Värdet på plats (mitten) = 25
Nu jämför vi nyckelelementet med mittelementet. Så (25 == 25), så vi har hittat nyckeln på plats (mitt).
Vi delar upp matrisen upprepade gånger och genom att jämföra nyckelelementet med mitten bestämmer vi i vilken hälft vi ska söka efter nyckeln.
Nedan följer C ++ och Java-implementeringen för binär sökning.
C ++ Implementering
#include #include using namespace std; int binarySearch(int myarray(), int beg, int end, int key) { int mid; if(end >= beg) { mid = (beg + end)/2; if(myarray(mid) == key) { return mid+1; } else if(myarray(mid) key; location = binarySearch(myarray, 0, 9, key); if(location != -1) { cout<<'Key found at location '< Produktion:
Inmatningsmatrisen är
5 8 10 13 21 23 25 43 54 75
Ange nyckeln som ska sökas: 21
Nyckel på plats 5
Java-implementering
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main(String() args) { int() myarray = {5,8,10,13,21,23,25,43,54,75}; int key, location = -1; System.out.println('The input array is'); for(int i=0;i= beg) { mid = (beg + end)/2; if(myarray(mid) == key) { return mid+1; } else if(myarray(mid) Produktion:
Inmatningsmatrisen är
5 8 10 13 21 23 25 43 54 75
vilka enheter som fungerar på osi lager 2
Ange nyckeln som ska sökas
tjugoett
nyckelns plats är 5
Binär sökning är effektivare när det gäller tid och korrekthet. Linjär sökteknik används sällan eftersom den är mer besvärlig och långsammare. Binär sökning är mycket snabbare jämfört med en linjär sökning.
Slutsats
Sökteknikerna hjälper oss att söka efter information lagrad på en dator så att användaren kan fortsätta med de andra uppgifterna för informationsbehandling. Linjär sökteknik är enkel och lättare men används inte i stor utsträckning.
Binär sökteknik är mycket snabbare och effektiv och används därför i stor utsträckning.
I vår kommande handledning kommer vi att utforska de olika sorteringsteknikerna i detalj.
=> Kolla in den perfekta C ++ träningsguiden här.
Rekommenderad läsning
- Introduktion till Java-programmeringsspråk - Videohandledning
- Introduktion till Appium Studio: Viktiga fördelar och funktioner
- Algoritmer i STL
- Bästa GRATIS C # -handledningsserie: Den ultimata C # -guiden för nybörjare
- JMeter Video 1: Introduktion, JMeter Ladda ner och installera
- Python introduktions- och installationsprocess
- Vad är Unix: En kort introduktion till Unix
- Introduktion till Micro Focus LoadRunner - Load Testing with LoadRunner Tutorial # 1
