Σειριακή και Δυαδική Αναζήτηση σε Πίνακα στη ΓΛΩΣΣΑ

Εισαγωγή

Η αναζήτηση ενός στοιχείου σε έναν πίνακα είναι μια από τις πιο συχνές λειτουργίες στον προγραμματισμό. Υπάρχουν δύο βασικές μέθοδοι αναζήτησης: η σειριακή αναζήτηση και η δυαδική αναζήτηση. Κάθε μέθοδος έχει τα δικά της πλεονεκτήματα και μειονεκτήματα, ανάλογα με την δομή των δεδομένων και τις απαιτήσεις του προγράμματος.

Στόχος αυτού του μαθήματος είναι να κατανοήσετε:

Τι είναι η σειριακή αναζήτηση και πώς υλοποιείται στη ΓΛΩΣΣΑ.
Τι είναι η δυαδική αναζήτηση και πώς υλοποιείται στη ΓΛΩΣΣΑ.
Ποια είναι τα πλεονεκτήματα και τα μειονεκτήματα κάθε μεθόδου.
Πότε να χρησιμοποιείτε κάθε μέθοδο.

Σειριακή Αναζήτηση

Ορισμός

Η σειριακή αναζήτηση (Linear Search) είναι μια μέθοδος αναζήτησης όπου ελέγχουμε κάθε στοιχείο του πίνακα ένα προς ένα, μέχρι να βρούμε το ζητούμενο στοιχείο ή μέχρι να φτάσουμε στο τέλος του πίνακα.

Χαρακτηριστικά

Απλή Υλοποίηση: Η σειριακή αναζήτηση είναι πολύ απλή στην υλοποίηση και δεν απαιτεί τον πίνακα να είναι ταξινομημένος.
Χρονική Πολυπλοκότητα: Η χρονική πολυπλοκότητα είναι O(n), όπου n είναι ο αριθμός των στοιχείων του πίνακα.
Χώρος Μνήμης: Δεν απαιτεί επιπλέον χώρο μνήμης.
Εφαρμογή: Ιδανική για μικρούς πίνακες ή μη ταξινομημένους πίνακες.

Αλγόριθμος Σειριακής Αναζήτησης

Ο αλγόριθμος της σειριακής αναζήτησης μπορεί να περιγραφεί ως εξής:

Ξεκινήστε από το πρώτο στοιχείο του πίνακα.
Συγκρίνετε το τρέχον στοιχείο με το ζητούμενο στοιχείο.
Αν το τρέχον στοιχείο είναι ίσο με το ζητούμενο, η αναζήτηση επιτυγχάνει.
Αν όχι, μετακινήστε στο επόμενο στοιχείο.
Επαναλάβετε μέχρι να βρείτε το στοιχείο ή να φτάσετε στο τέλος του πίνακα.

Παράδειγμα: Ένα πρόγραμμα που αναζητά ένα στοιχείο σε έναν πίνακα χρησιμοποιώντας σειριακή αναζήτηση:

ΠΡΟΓΡΑΜΜΑ Σειριακή_Αναζήτηση
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: π[10], i, α, βρέθηκε
ΑΡΧΗ
  ! Διάβασε τα στοιχεία του πίνακα
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 10
    ΓΡΑΨΕ 'Δώσε το ', i, '-οστό στοιχείο: '
    ΔΙΑΒΑΣΕ π[i]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  
  ! Διάβασε το στοιχείο που ψάχνουμε
  ΓΡΑΨΕ 'Δώσε το στοιχείο που ψάχνεις: '
  ΔΙΑΒΑΣΕ α
  
  ! Αναζήτηση
  βρέθηκε ← 0
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 10
    ΑΝ π[i] = α ΤΟΤΕ
      βρέθηκε ← 1
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  
  ! Εκτύπωση αποτελέσματος
  ΑΝ βρέθηκε = 1 ΤΟΤΕ
    ΓΡΑΨΕ 'Το στοιχείο βρέθηκε.'
  ΑΛΛΙΩΣ
    ΓΡΑΨΕ 'Το στοιχείο δεν βρέθηκε.'
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

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

Ορισμός

Η δυαδική αναζήτηση (Binary Search) είναι μια μέθοδος αναζήτησης που εφαρμόζεται σε ταξινομημένους πίνακες. Χωρίζει επαναληπτικά τον πίνακα στη μέση και συγκρίνει το μεσαίο στοιχείο με το ζητούμενο στοιχείο, για να αποφασίσει σε ποιο μισό του πίνακα να συνεχίσει την αναζήτηση.

Χαρακτηριστικά

Προαπαιτούμενο: Ο πίνακας πρέπει να είναι ταξινομημένος.
Χρονική Πολυπλοκότητα: Η χρονική πολυπλοκότητα είναι O(log n), όπου n είναι ο αριθμός των στοιχείων του πίνακα.
Χώρος Μνήμης: Δεν απαιτεί επιπλέον χώρο μνήμης.
Εφαρμογή: Ιδανική για μεγάλους ταξινομημένους πίνακες.

Αλγόριθμος Δυαδικής Αναζήτησης

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

Ορίστε δύο δείκτες, αριστερό και δεξιό, που προσδιορίζουν το τρέχον υποπίνακα αναζήτησης.
Υπολογίστε τον μεσαίο δείκτη: μέσος ← (αριστερό + δεξιό) DIV 2.
Συγκρίνετε το μεσαίο στοιχείο με το ζητούμενο στοιχείο:

Αν είναι ίσο, η αναζήτηση επιτυγχάνει.
Αν το ζητούμενο είναι μικρότερο, συνεχίστε την αναζήτηση στο αριστερό μισό.
Αν το ζητούμενο είναι μεγαλύτερο, συνεχίστε την αναζήτηση στο δεξιό μισό.

Επαναλάβετε μέχρι να βρείτε το στοιχείο ή μέχρι να γίνει ο αριστερός δείκτης μεγαλύτερος από τον δεξιό.

Παράδειγμα: Ένα πρόγραμμα που αναζητά ένα στοιχείο σε έναν ταξινομημένο πίνακα χρησιμοποιώντας δυαδική αναζήτηση:

ΠΡΟΓΡΑΜΜΑ Δυαδική_Αναζήτηση
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: π[10], αριστερό, δεξιό, μέσος, α, βρέθηκε
ΑΡΧΗ
  ! Διάβασε τα στοιχεία του ταξινομημένου πίνακα
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 10
    ΓΡΑΨΕ 'Δώσε το ', i, '-οστό στοιχείο (ταξινομημένο): '
    ΔΙΑΒΑΣΕ π[i]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  
  ! Διάβασε το στοιχείο που ψάχνουμε
  ΓΡΑΨΕ 'Δώσε το στοιχείο που ψάχνεις: '
  ΔΙΑΒΑΣΕ α
  
  ! Αρχικοποίηση δεικτών
  αριστερό ← 1
  δεξιό ← 10
  βρέθηκε ← 0
  
  ! Δυαδική αναζήτηση
  ΟΣΟ αριστερό <= δεξιό ΚΑΙ βρέθηκε = 0 ΕΠΑΝΑΛΑΒΕ
    μέσος ← (αριστερό + δεξιό) DIV 2
    ΑΝ π[μέσος] = α ΤΟΤΕ
      βρέθηκε ← 1
    ΑΛΛΙΩΣ_ΑΝ α < π[μέσος] ΤΟΤΕ
      δεξιό ← μέσος - 1
    ΑΛΛΙΩΣ
      αριστερό ← μέσος + 1
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  
  ! Εκτύπωση αποτελέσματος
  ΑΝ βρέθηκε = 1 ΤΟΤΕ
    ΓΡΑΨΕ 'Το στοιχείο βρέθηκε.'
  ΑΛΛΙΩΣ
    ΓΡΑΨΕ 'Το στοιχείο δεν βρέθηκε.'
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

Σύγκριση Μεθόδων Αναζήτησης

Σύγκριση Σειριακής και Δυαδικής Αναζήτησης

Χαρακτηριστικό	Σειριακή Αναζήτηση	Δυαδική Αναζήτηση
Προαπαιτούμενο	Ο πίνακας δεν χρειάζεται να είναι ταξινομημένος.	Ο πίνακας πρέπει να είναι ταξινομημένος.
Χρονική Πολυπλοκότητα	O(n)	O(log n)
Υλοποίηση	Απλή	Πιο σύνθετη
Χώρος Μνήμης	Δεν απαιτεί επιπλέον χώρο	Δεν απαιτεί επιπλέον χώρο
Εφαρμογή	Μικροί πίνακες, μη ταξινομημένοι πίνακες	Μεγάλοι ταξινομημένοι πίνακες

Ποια Μέθοδος να Επιλέξω;

Η επιλογή μεταξύ σειριακής και δυαδικής αναζήτησης εξαρτάται από τις ακόλουθες παραμέτρους:

Μέγεθος Πίνακα: Για μικρούς πίνακες, η σειριακή αναζήτηση μπορεί να είναι αρκετά αποτελεσματική. Για μεγάλους πίνακες, η δυαδική αναζήτηση είναι πιο αποδοτική.
Ταξινόμηση: Αν ο πίνακας δεν είναι ταξινομημένος, η δυαδική αναζήτηση δεν μπορεί να χρησιμοποιηθεί.
Συχνότητα Αναζήτησης: Αν οι αναζητήσεις είναι συχνές, η δυαδική αναζήτηση είναι προτιμότερη (εφόσον ο πίνακας είναι ταξινομημένος).
Κόστος Ταξινόμησης: Αν ο πίνακας πρέπει να ταξινομηθεί για να χρησιμοποιηθεί η δυαδική αναζήτηση, το κόστος της ταξινόμησης πρέπει να ληφθεί υπόψη.

Παραδείγματα Αναζήτησης

Παράδειγμα 1: Σειριακή Αναζήτηση σε Πίνακα Βαθμολογιών

Ένα πρόγραμμα που αναζητά μια συγκεκριμένη βαθμολογία σε έναν πίνακα βαθμολογιών μαθητών:

ΠΡΟΓΡΑΜΜΑ Αναζήτηση_Βαθμολογίας
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: βαθμοί[20], i, α, βρέθηκε
ΑΡΧΗ
  ! Διάβασε τις βαθμολογίες
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 20
    ΓΡΑΨΕ 'Δώσε τον βαθμό του ', i, '-ου μαθητή: '
    ΔΙΑΒΑΣΕ βαθμοί[i]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  
  ! Διάβασε τη βαθμολογία που ψάχνουμε
  ΓΡΑΨΕ 'Δώσε τη βαθμολογία που ψάχνεις: '
  ΔΙΑΒΑΣΕ α
  
  ! Αναζήτηση
  βρέθηκε ← 0
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 20
    ΑΝ βαθμοί[i] = α ΤΟΤΕ
      βρέθηκε ← 1
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  
  ! Εκτύπωση αποτελέσματος
  ΑΝ βρέθηκε = 1 ΤΟΤΕ
    ΓΡΑΨΕ 'Η βαθμολογία βρέθηκε.'
  ΑΛΛΙΩΣ
    ΓΡΑΨΕ 'Η βαθμολογία δεν βρέθηκε.'
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

Παράδειγμα 2: Δυαδική Αναζήτηση σε Ταξινομημένο Πίνακα

Ένα πρόγραμμα που αναζητά έναν αριθμό σε έναν ταξινομημένο πίνακα χρησιμοποιώντας δυαδική αναζήτηση:

ΠΡΟΓΡΑΜΜΑ Δυαδική_Αναζήτηση_Αριθμού
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: π[15], αριστερό, δεξιό, μέσος, α, βρέθηκε, i
ΑΡΧΗ
  ! Διάβασε τα ταξινομημένα στοιχεία του πίνακα
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 15
    ΓΡΑΨΕ 'Δώσε το ', i, '-οστό ταξινομημένο στοιχείο: '
    ΔΙΑΒΑΣΕ π[i]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  
  ! Διάβασε τον αριθμό που ψάχνουμε
  ΓΡΑΨΕ 'Δώσε τον αριθμό που ψάχνεις: '
  ΔΙΑΒΑΣΕ α
  
  ! Αρχικοποίηση δεικτών
  αριστερό ← 1
  δεξιό ← 15
  βρέθηκε ← 0
  
  ! Δυαδική αναζήτηση
  ΟΣΟ αριστερό <= δεξιό ΚΑΙ βρέθηκε = 0 ΕΠΑΝΑΛΑΒΕ
    μέσος ← (αριστερό + δεξιό) DIV 2
    ΑΝ π[μέσος] = α ΤΟΤΕ
      βρέθηκε ← 1
    ΑΛΛΙΩΣ_ΑΝ α < π[μέσος] ΤΟΤΕ
      δεξιό ← μέσος - 1
    ΑΛΛΙΩΣ
      αριστερό ← μέσος + 1
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  
  ! Εκτύπωση αποτελέσματος
  ΑΝ βρέθηκε = 1 ΤΟΤΕ
    ΓΡΑΨΕ 'Ο αριθμός βρέθηκε.'
  ΑΛΛΙΩΣ
    ΓΡΑΨΕ 'Ο αριθμός δεν βρέθηκε.'
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

Παράδειγμα 3: Σύγκριση Σειριακής και Δυαδικής Αναζήτησης

Ένα πρόγραμμα που συγκρίνει τις δύο μεθόδους αναζήτησης σε έναν ταξινομημένο πίνακα:

ΠΡΟΓΡΑΜΜΑ Σύγκριση_Αναζήτησης
ΜΕΤΑΒΛΗΤΕΣ
  ΑΚΕΡΑΙΕΣ: π[20], i, α, βρέθηκε_σειριακή, βρέθηκε_δυαδική, αριστερό, δεξιό, μέσος
ΑΡΧΗ
  ! Διάβασε τα ταξινομημένα στοιχεία του πίνακα
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 20
    ΓΡΑΨΕ 'Δώσε το ', i, '-οστό ταξινομημένο στοιχείο: '
    ΔΙΑΒΑΣΕ π[i]
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  
  ! Διάβασε τον αριθμό που ψάχνουμε
  ΓΡΑΨΕ 'Δώσε τον αριθμό που ψάχνεις: '
  ΔΙΑΒΑΣΕ α
  
  ! Σειριακή Αναζήτηση
  βρέθηκε_σειριακή ← 0
  ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 20
    ΑΝ π[i] = α ΤΟΤΕ
      βρέθηκε_σειριακή ← 1
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  
  ! Δυαδική Αναζήτηση
  αριστερό ← 1
  δεξιό ← 20
  βρέθηκε_δυαδική ← 0
  ΟΣΟ αριστερό <= δεξιό ΚΑΙ βρέθηκε_δυαδική = 0 ΕΠΑΝΑΛΑΒΕ
    μέσος ← (αριστερό + δεξιό) DIV 2
    ΑΝ π[μέσος] = α ΤΟΤΕ
      βρέθηκε_δυαδική ← 1
    ΑΛΛΙΩΣ_ΑΝ α < π[μέσος] ΤΟΤΕ
      δεξιό ← μέσος - 1
    ΑΛΛΙΩΣ
      αριστερό ← μέσος + 1
    ΤΕΛΟΣ_ΑΝ
  ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  
  ! Εκτύπωση αποτελεσμάτων
  ΓΡΑΨΕ 'Σειριακή Αναζήτηση: '
  ΑΝ βρέθηκε_σειριακή = 1 ΤΟΤΕ
    ΓΡΑΨΕ 'Βρέθηκε'
  ΑΛΛΙΩΣ
    ΓΡΑΨΕ 'Δεν βρέθηκε'
  ΤΕΛΟΣ_ΑΝ
  
  ΓΡΑΨΕ 'Δυαδική Αναζήτηση: '
  ΑΝ βρέθηκε_δυαδική = 1 ΤΟΤΕ
    ΓΡΑΨΕ 'Βρέθηκε'
  ΑΛΛΙΩΣ
    ΓΡΑΨΕ 'Δεν βρέθηκε'
  ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

Ασκήσεις

Άσκηση 1: Σειριακή Αναζήτηση

Να γράψετε ένα πρόγραμμα στη ΓΛΩΣΣΑ που να διαβάζει 10 αριθμούς από τον χρήστη, να τους αποθηκεύει σε έναν πίνακα και να αναζητά αν ένας αριθμός που θα δώσει ο χρήστης υπάρχει στον πίνακα χρησιμοποιώντας σειριακή αναζήτηση.

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

Να γράψετε ένα πρόγραμμα στη ΓΛΩΣΣΑ που να διαβάζει 15 ταξινομημένους αριθμούς από τον χρήστη, να τους αποθηκεύει σε έναν πίνακα και να αναζητά αν ένας αριθμός που θα δώσει ο χρήστης υπάρχει στον πίνακα χρησιμοποιώντας δυαδική αναζήτηση.

Άσκηση 3: Σειριακή Αναζήτηση με Μέτρηση

Να γράψετε ένα πρόγραμμα στη ΓΛΩΣΣΑ που να διαβάζει 12 αριθμούς από τον χρήστη, να τους αποθηκεύει σε έναν πίνακα και να αναζητά πόσες φορές εμφανίζεται ένας αριθμός που θα δώσει ο χρήστης.

Άσκηση 4: Δυαδική Αναζήτηση με Θέση

Να γράψετε ένα πρόγραμμα στη ΓΛΩΣΣΑ που να διαβάζει 20 ταξινομημένους αριθμούς από τον χρήστη, να τους αποθηκεύει σε έναν πίνακα και να αναζητά τη θέση ενός αριθμού που θα δώσει ο χρήστης χρησιμοποιώντας δυαδική αναζήτηση.

Άσκηση 5: Σύγκριση Μεθόδων

Να γράψετε ένα πρόγραμμα στη ΓΛΩΣΣΑ που να διαβάζει 10 ταξινομημένους αριθμούς από τον χρήστη, να τους αποθηκεύει σε έναν πίνακα και να αναζητά έναν αριθμό χρησιμοποιώντας και τις δύο μεθόδους (σειριακή και δυαδική). Να εκτυπώνει το αποτέλεσμα και για τις δύο μεθόδους.

Άσκηση 6: Αναζήτηση σε Πίνακα Βαθμολογιών

Να γράψετε ένα πρόγραμμα στη ΓΛΩΣΣΑ που να διαβάζει τις βαθμολογίες 15 μαθητών, να τις αποθηκεύει σε έναν πίνακα και να αναζητά αν ένας μαθητής έχει μια συγκεκριμένη βαθμολογία χρησιμοποιώντας σειριακή αναζήτηση.

Άσκηση 7: Δυαδική Αναζήτηση σε Πίνακα Ονομάτων

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

Άσκηση 8: Αναζήτηση με Εύρος

Να γράψετε ένα πρόγραμμα στη ΓΛΩΣΣΑ που να διαβάζει 20 ταξινομημένους αριθμούς από τον χρήστη, να τους αποθηκεύει σε έναν πίνακα και να αναζητά αν υπάρχει ένας αριθμός μέσα σε ένα εύρος που θα δώσει ο χρήστης (π.χ. μεταξύ 10 και 20).