Programming In C: Δυαδική Αναζήτηση

Δυαδική Αναζήτηση

Ο αλγόριθμος της δυαδικής αναζήτησης μπορεί να εφαρμοστεί για να αναζητηθεί μία τιμή σε ένα ταξινομημένο πίνακα ανεξαρτήτως με ποια σειρά έχει ταξινομηθεί. Ο αλγόριθμος έχει συγκεκριμένα βήματα για την εκτέλεση του.

Δηλώνουμε τρεις μεταβλητές :

1.
I. Μια , η οποία δείχνει την αρχή του πίνακα.

II. Μια άλλη , η οποία δείχνει το τέλος του πίνακα.

III. Μια τελευταία , η οποία δείχνει την μέση του πίνακα (βρίσκοντας την αν προσθέσουμε τις μεταβλητής αρχής και τέλους του πίνακα δια του δύο)

2. Ελέγχουμε αν το στοιχείο που αναζητούμε είναι ίσο με την μεταβλητή η οποία δείχνει στην μέση του πίνακα.

I. Αν είναι ίσα τότε βρήκαμε το στοιχείο που αναζητούσαμε και τερματίζεται η αναζήτηση.

II. Αν το στοιχείο είναι μεγαλύτερο από το μεσαίο στοιχείο του πίνακα τότε , ορίζουμε την αρχή του πίνακα από την θέση του στοιχείου της μέσης συν άλλη μία θέση και η αναζήτηση επιστρέφει από το ΒΗΜΑ 1.

III. Αν το στοιχείο είναι μικρότερο από το μεσαίο στοιχείο του πίνακα τότε ορίζουμε το τέλος του πίνακα από την θέση του στοιχείου της μέσης μείον μία θέση και η αναζήτηση επιστρέφει από το ΒΗΜΑ 1.

Παράδειγμα :

Να γραφτεί πρόγραμμα το οποίο να δηλώνεται έναν πίνακα μεγέθους 7 ακεραίων με ταξινομημένες τιμές κατά αύξουσα σειρά. Να διαβάζει ένα ακέραιο και να εμφανίζει την θέση μέσα στο πίνακα , αν δεν βρεθεί να εμφανίζει σχετικό μήνυμα. Η επιστροφή της θέσης να γίνεται μέσω συνάρτησης η οποία θα δέχεται σαν ορίσματα τον πίνακα, το μέγεθος του και τον ακέραιο που διαβάστηκε. Αν βρεθεί μέσα στο πίνακα το στοιχείο να επιστρέφει την θέση του , αλλιώς να επιστρέφει την τιμή -1.

Λύση :

#include<stdio.h>
#include<stdlib.h>

int diadiki_anazitisi (int arr[],int lenght ,int num);

int main(void)
{

	int noumero,thesi;
	int pinakas[7]={5,10,15,20,25,30,35};

 	printf("Dose enan akeraio \n");
	scanf("%d",&noumero);
	thesi=diadiki_anazitisi(pinakas,7,noumero);
	if(thesi == -1)
	{
		printf("Den bre8ike o ari8mos mesa sto pinaka\n");
	}
	else
	{
		printf("Bre9ike to %d stin thesi %d \n"num,thesi);
	}
	system("pause");
	return 0;
}

int diadiki_anazitisi (int arr[],int lenght ,int num)
{
	int arxi,mesi,telos; 

	arxi=0;
	telos=lenght-1;
	while(arxi<=telos)
	{
		mesi=(arxi+telos)/2;
		if(num<arr[mesi])
		{
			telos=telos-1;
		}
		else if (num>arr[mesi])
		{
			arxi=arxi+1;
		}
		else 
		{
			return mesi;
		}
	}

	return -1;
}