Binary search

[ClouD]

Έχω ως έργασια να υλοποιήσω έναν αλγόριθμο που να κάνει binary search σε ταξινομημένη λίστα. Το πρόβλημα είναι ότι υποτίθεται να πηγαίνει στο μεσαίο στοιχείο της λίστας χωρίζοντας την και ύστερα στο μεσαίο σε μία από τις δύο από τις υπολίστες, μετά πάλι το ίδιο μέχρι να βρεθεί το στοιχείο. Όταν η λίστα έχει έξι στοιχεία, πως βρίσκει μεσαίο ? Ποιο θα θεωρούνταν μεσαίο αν ο αλγόριθμος ήταν πρόγραμμα ?

 

Ελπίζω να τα είπα αρκετά καθαρά, αν όχι ρωτήστε με να τα διευκρινήσω, δεν ξέρω αρκετά καλά για να το κάνω από μόνος

 

Ευχαριστώ.

[Dyolf]

#include <stdio.h>

main( )

{

int A[10]; /* Υποθέτουμε ότι ο πίνακας έχει στοιχεία και είναι ταξινομημένος */

int M,K,S,i,e,left,right; /* Μ : Κρατάει την θέση του πίνακα */

K=0; /* Κ : Κρατάει την θέση του στοιχείου μας */

e=0; /* e : Βοηθητική μεταβλητή για να ελέγχουμε αν βρήκαμε το στοιχείο */

left=0; /* left, right : Τα όρια του πίνακα */

right=9;

printf("\nDwse stoixeio gia anazitisi:");

scanf("%d", &S); /* Βάζουμε το στοιχείο που θέλουμε να βρούμε */

while (left<=right)

{

M =(left+right)/2; /* Ξεκινάμε από την θέση 4 του πίνακα την αναζήτηση */

if (A[M]==S)

{

K=M;

e=1; /* Βρέθηκε το στοιχείο

break; /* Βγαίνουμε από την επανάληψη μας */

}

if (A[M]<S)

left=M+1;

else

right=M-1;

}

if (e==0)

printf ("\nDen vrethike to stoixeio.\n");

else

{

printf ("\nTo stoixeio vrethike sthn thesi: ");

printf ("%d\n", K);

}

}

 

Αυτός είναι ο κώδικας σε C σε περίπτωση που τον θέλεις...

Επειδή τα left,right είναι ακέραιοι, κόβεται το δεκαδικό τους μέρος. Αν δηλαδή ο πινακάς έχει 6 στοιχεία το μεσαίο θα είναι το 3ο. Αν έχει 7, θα είναι πάλι το 3 (7/2=3,5 αλλά κόβεται το δεκαδικό μέρος)

Ελπίζω να βοήθησα

[ClouD]

Σκέφτηκα να κάνω μια δομή επιλογής, ώστε όταν είναι άρτιος μόνο να πηγαίνει έτσι , και όταν δεν είναι να επιλέγει απλά το μεσαίο. Αλλά ύστερα γενικά δεν μπορώ να βρώ έναν τρόπο να εκφράσω κάτι στη συνέχεια της άσκησης, άρα είναι ψιλολάθος αυτό που κάνω. Ευχαριστώ πολύ.Παρεπιπτόντως αυτό το τραγούδι ακούω τώρα (ξέρεις που έχει τον ωραίο στίχο της υπογραφής σου)