En av de mest grundläggande algoritmerna inom datavetenskap är den binära sökalgoritmen. Du kan implementera binär sökning med två metoder: den iterativa metoden och den rekursiva metoden. Medan båda metoderna har samma tidskomplexitet är den iterativa metoden mycket mer effektiv när det gäller rymdkomplexitet.

Den iterativa metoden har en rymdkomplexitet av O(1) jämfört med O(logga) produceras med den rekursiva metoden. Så, hur kan du implementera den binära sökalgoritmen med den iterativa metoden i C, C++ och Python?

Vad är binär sökning?

Binär sökning även känd som halvintervallssökning, logaritmisk sökning eller binär chop är en algoritm som söker och returnerar positionen för ett element i en sorterad array. Sökelementet jämförs med mittelementet. Om du tar medelvärdet av de nedre och övre gränserna kan du hitta mittelementen.

Om sökelementet är större än mittelementet betyder det att alla element på vänster sida är mindre än sökelementet. Så kontrollen skiftar till höger sida av arrayen (om arrayen är i stigande ordning) genom att öka den nedre gränsen till nästa position för mittelementet.

instagram viewer

På samma sätt, om sökelementet är mindre än mittelementet, betyder det att alla element på höger sida är större än sökelementet. Så, kontrollen skiftar till den vänstra delen av arrayen genom att ändra den övre gränsen till den tidigare positionen för mittelementet.

Detta minskar antalet jämförelser drastiskt jämfört med implementering av linjär sökning där antalet jämförelser är lika med antalet element i det värsta scenariot. Denna metod visar sig vara mycket användbar för att hitta nummer i en telefonbok eller ord i en ordbok.

Här är en schematisk representation av Binär sökalgoritm:

Binär sökning med C

Följ dessa steg för att implementera binär sökning med C:

Hela källkoden för det binära sökprogrammet som använder C, C++, Java och Python finns i detta GitHub-förråd.

Programmet definierar en funktion, binarySearch(), som returnerar antingen indexet för det hittade värdet eller -1 om det inte finns:

#omfatta <stdio.h>
intbinär sökning(int arr[], int arr_size, int söknummer){
/*... */
}

Funktionen fungerar genom att iterativt begränsa sökutrymmet. Eftersom binär sökning fungerar på sorterade arrayer kan du beräkna mitten som annars inte är vettigt. Du kan antingen be användaren om en sorterad array eller använda sorteringsalgoritmer som Bubble eller Selection sort.

De låg och hög variabler lagrar indexen som representerar gränserna för det aktuella sökutrymmet. mitten lagrar indexet i mitten:

int låg = 0, hög = arr_size - 1, mitten;

Den huvudsakliga medan() loop kommer att begränsa sökutrymmet. Om värdet på det låga indexet någonsin blir större än det höga indexet, har sökutrymmet tagit slut, så värdet kan inte finnas.

medan (låg <= hög) {
/* fortsätter... [1] */
 }
lämna tillbaka-1;

Efter att ha uppdaterat mittpunkten i början av loopen finns det tre möjliga utfall:

  1. Om värdet i mitten är det vi letar efter, returnera det indexet.
  2. Om mittpunktsvärdet är större än det vi letar efter, minska det höga.
  3. Om mittpunktsvärdet är mindre, öka det låga. 
/* [1] ...fortsättning */
 mid = (låg + (hög - låg)) / 2;
if (arr[mid] == söknummer)
lämna tillbaka mitten;
annanom (arr[mid] > söknummer)
 hög = mitten - 1;
annan
 låg = mitten + 1;

Testa funktionen med användarinmatning. Använda sig av scanf() för att få indata från kommandoraden, inklusive arraystorleken, dess innehåll och ett nummer att söka efter:

inthuvud(){
int arr[100], i, arr_size, search_number;
 printf("Ange antal element: ");
 scanf("%d", &arr_size);
 printf("Vänligen ange siffror: ");
för (i = 0; i < arr_size; i++) {
 scanf("%d", &arr[i]);
 }


printf("Ange nummer som ska sökas: ");
 scanf("%d", &söknummer);


i = binär sökning (arr, arr_size, search_number);


om (i==-1)
 printf("Nummer inte närvarande");
annan
 printf("Numret finns på position %d"i + 1);
lämna tillbaka0;
}

Om du hittar numret, visa dess position eller index, annars ett meddelande som säger att numret inte finns.

Binär sökning med C++

Du kan konvertera C-programmet till ett C++-program genom att importera Input Output Stream och använd namnutrymme std för att undvika att upprepa det flera gånger under programmets gång.

#omfatta <iostream>
använder sig av namnutrymmestd;

Använda sig av cout med utsugsoperatör << istället för printf() och cin med insättningsoperator >> istället för scanf() och ditt C++-program är klart.

printf("Ange antal element: ");
cout <<"Ange antal element: ";
scanf("%d", &arr_size);
cin >> arr_size;

Binär sökning med Python

Eftersom Python inte har inbyggt stöd för arrayer, använd listor. Definiera en funktion, binarySearch(), som accepterar tre parametrar, listan, dess storlek och ett nummer att söka efter:

defbinär sökning(arr, arr_size, search_number):
 låg = 0
 hög = arr_size - 1
medan låg <= hög:
 mellan = låg + (hög-låg)//2
 om arr[mid] == söknummer:
lämna tillbaka mitten
elif arr[mid] > söknummer:
 hög = mitten - 1
annan:
 låg = mitten + 1
lämna tillbaka-1

Initiera två variabler, låg och hög, för att fungera som den nedre och övre gränsen för listan. I likhet med C-implementeringen, använd a medan slinga som begränsar sökutrymmet. Initiera mitten för att lagra mittvärdet i listan. Python tillhandahåller våningsindelningsoperatorn(//) som ger största möjliga heltal.

Gör jämförelserna och begränsa sökutrymmet tills mittvärdet är lika med söknumret. Om söknumret inte finns kommer kontrollen tillbaka -1.

arr_size = int (ingång("Ange antal element: "))
arr=[]
skriva ut("Vänligen ange siffror: ", slut="")
för i inom intervallet (0,arr_size):
 arr.append(int(inmatning()))
söknummer = int (ingång("Ange nummer som ska sökas: "))
resultat = binär sökning (arr, arr_size, search_number)
om resultat == -1:
 skriva ut("Nummer inte närvarande")
annan:
 print("Nummer är närvarande vid position ", (resultat + 1))

Testa funktionen med användarinmatning. Använda sig av inmatning() för att få liststorleken, dess innehåll och ett nummer att söka efter. Använda sig av int() för att typcasta stränginmatningen som accepteras av Python som standard till ett heltal. För att lägga till nummer till listan, använd bifoga() fungera.

Ring upp binarySearch() och förmedla argumenten. Om du hittar numret, visa dess position eller index, annars ett meddelande som säger att numret inte finns.

Utdata från binär sökalgoritm

Följande är utdata från den binära sökalgoritmen när elementet finns i arrayen:

Följande är utdata från den binära sökalgoritmen när elementet inte finns i arrayen:

Lär dig de grundläggande datastrukturerna och algoritmerna

Sökning är en av de första algoritmerna du lär dig och tillfrågas ofta i kodningstävlingar, placeringar och intervjuer. Några andra algoritmer du bör lära dig är algoritmer för sortering, hashning, dynamisk programmering, strängmatchning och primalitetstestning.

Dessutom är det viktigt att förstå tids- och rumskomplexiteten hos algoritmer. De är ett av de mest avgörande begreppen inom datavetenskap för att bestämma effektiviteten hos någon algoritm. Med kunskap om datastrukturer och algoritmer är du skyldig att bygga de bästa programmen.