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

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

Έστω οτι θέλουμε να δούμε αν υπάρχει το όνομα “Γιώργος”σε πίνακας Π[100] και αν υπάρχει να εμφανίζεται ο αριθμός του κελιού στο οποίο εντοπίστηκε. Υπάρχουν διάφορες παραλλαγές τη σειριακής αναζήτησης που θα δούμε παρακάτω.

Περίπτωση 1
Ο πίνακας δεν είναι ταξινομημένος και το όνομα “Γιώργος” μπορεί να μην υπάρχει ή αν υπάρχει να εμφανίζεται τουλάχιστον μία φορά.  

				
					Αλγόριθμος περ1
Για i απο 1 μεχρι 100
   Αν Π[i]="Γιώργος" τοτε
      Εμφάνισε i
   Τέλος_αν
Τέλος_επαναληψης
Τέλος περ1

Περίπτωση 2
Ο πίνακας δεν είναι ταξινομημένος και το όνομα “Γιώργος” εμφανίζεται το πολύ μία φορά. Μπορεί να χρησιμοποιηθεί ο προηγούμενος αλγόριθμος αλλά υπάρχει ταχύτερος.

				
					Αλγόριθμος περ1
i <- 1
flag <- ψευδής
Όσο i<=100 και flag=ψευδής επανάλαβε  
   Αν Π[i]="Γιώργος" τοτε
      Εμφάνισε i
      flag <- αληθής
   αλλιώς
      i <- i + 1
   Τέλος_αν
Τέλος_επαναληψης
Τέλος περ1

Περίπτωση 3
Ο πίνακας είναι ταξινομημένος αλφαβητικά (αύξουσα) και το όνομα “Γιώργος” εμφανίζεται καμία, μία ή περισσότερες φορές. Μπορεί να χρησιμοποιηθεί ο προηγούμενος αλγόριθμος αλλά υπάρχει ταχύτερος.

				
					Αλγόριθμος περ1
i <- 1
Όσο i<=100 και Π[i]<="Γιώργος" επανάλαβε
   Αν Π[i]="Γιώργος" τοτε
      Εμφάνισε i
   αλλιώς
      i <- i + 1
   Τέλος_αν
Τέλος_επαναληψης
Τέλος περ1

Περίπτωση 4
Ο πίνακας είναι ταξινομημένος αλφαβητικά (αύξουσα) και το όνομα “Γιώργος” εμφανίζεται ακριβώς μία φορά.

				
					Αλγόριθμος περ1
i <- 1
flag <- ψευδής
Όσο flag=ψευδής επανάλαβε
   Αν Π[i]="Γιώργος" τοτε
      Εμφάνισε i
      flag <- αληθής
   αλλιώς
      i <- i + 1
   Τέλος_αν
Τέλος_επαναληψης
Τέλος περ1

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

Ο αλγόριθμος της δυαδικής αναζήτησης (binary search) εφαρμόζεται μόνο σε ταξινομημένους πίνακες. Αν ο πίνακας δεν είναι ταξινομημένος, τότε θα πρέπει να χρησιμοιήσουμε την σειραική αναζήτηση.

Ο αλγόριθμος λειτουργεί ως εξής:

  • Βρίσκουμε το μεσαίο στοιχείο του ταξινομημένου πίνακα.
  • Εάν το προς αναζήτηση στοιχείο είναι ίσο με το μεσαίο στοιχείο, τότε σταματάμε την αναζήτηση αφού το
    στοιχείο βρέθηκε.
  • Εάν δε βρέθηκε, τότε ελέγχουμε αν το στοιχείο που αναζητούμε είναι μικρότερο ή μεγαλύτερο από το
    μεσαίο στοιχείο του πίνακα. Αν είναι μικρότερο, περιορίζουμε την αναζήτηση στο πρώτο μισό του πίνακα
    (με την προϋπόθεση ότι τα στοιχεία είναι διατεταγμένα κατά αύξουσα σειρά), ενώ αν είναι μεγαλύτερο
    περιορίζουμε την αναζήτηση στο δεύτερο μισό του πίνακα.
  • Η διαδικασία αυτή επαναλαμβάνεται για το κατάλληλο πρώτο ή δεύτερο μισό του πίνακα, μετά για το 1/4
    του πίνακα κ.ο.κ. μέχρι, είτε να βρεθεί το στοιχείο, είτε να μην είναι δυνατό να χωρισθεί ο πίνακας
    περαιτέρω σε δύο νέα μέρη.

Ακολουθεί ο κώδικας της δυαδικής αναζήτησης του στοιχείου key σε ταξινομημένο πίνακα Α[20].  

				
					Αλγόριθμος Δυαδική_αναζήτηση     !Αναζήτηση του key σε πίνακα A[20]
Α ← 1                            ! αριστερό όριο
Δ ← 20                           ! δεξιό όριο
Flag ← FALSE
Διάβασε key
Όσο (Α ≤ Δ) και (Flag = FALSE) επανάλαβε
    M ← (Α + Δ) div 2
    Αν A[M] = key τότε
        Flag ← TRUE
    αλλιώς_αν A[M] < key τότε
        A ← M + 1
    αλλιώς
        Δ ← M - 1
    Τέλος_αν
Τέλος_επανάληψης

Αν Flag = TRUE τότε
    Εμφάνισε "Το στοιχείο,", key, "υπάρχει στη θέση:", Μ
αλλιώς
    Εμφάνισε "Το στοιχείο,", key, " δεν υπάρχει στον πίνακα"
Τέλος_αν
Τέλος Δυαδική_αναζήτηση

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

Στην παρακάτω διαδραστική εφαρμογή μπορείτε να κάνετε δυαδική αναζήτηση με οποιοδήποτε αριθμό και να δείτε τα βήματα που ακολουθούνται.

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

Πληκτρολογήστε τον αριθμό που θέλετε να αναζητήσετε:


Ερωτήσεις ανάπτυξης απο Πανελλαδικές εξετάσεις

  1. (Ε2005-Θ1E) Αναφέρατε τις περιπτώσεις που δικαιολογείται η χρήση του αλγορίθμου της σειριακής αναζήτησης.
  2. (2013-A3β, B2013-A3β) Να γράψετε τις περιπτώσεις για τις οποίες δικαιολογείται η χρήση της σειριακής μεθόδου αναζήτησης σε έναν πίνακα.
  3. (E2017-A3β, ΕΕ2017-A3β) Ποιοι είναι οι δύο πλέον διαδεδομένοι αλγόριθμοι αναζήτησης; Ποιος είναι ο πλέον αποδοτικός και τι περιορισμό έχει;
  4. (ΕΒ2006-Θ1Δ) Δίνεται μονοδιάστατος μη ταξινομημένος πίνακας Τ με Ν διαφορετικά στοιχεία. Να γράψετε τον αλγόριθμο σειριακής αναζήτησης της τιμής μιας μεταβλητής key στον πίνακα Τ.
  5. (Ε2018-A3α, ΕΞ2018-A3α) Να αναφέρετε δύο περιπτώσεις στις οποίες συνίσταται η χρήση σειριακής αναζήτησης σε ταξινομημένο πίνακα.
  6. (E2011-Θ Α5, ΕΒ2011-Θ Α5) Δίνεται ο παρακάτω ημιτελής αλγόριθμος αναζήτησης ενός αριθμού key σε έναν αριθμητικό πίνακα table Ν στοιχείων, στον οποίο ο key μπορεί να εμφανίζεται περισσότερες από μία φορές. 
    Αλγόριθμος Αναζήτηση
Δεδομένα // table, Ν, key //
Βρέθηκε ← Ψευδής
ΔενΒρέθηκε ← ....................
i ← 1
Όσο ΔενΒρέθηκε = Αληθής και i <= Ν επανάλαβε
    Αν .................... τότε
        Εμφάνισε "Βρέθηκε στη θέση", i
        Βρέθηκε ← ....................
    Αλλιώς_αν .................... τότε
        ΔενΒρέθηκε ← ....................
    Τέλος_αν
    i ← i + 1
Τέλος_επανάληψης
Αποτελέσματα // Βρέθηκε //
Τέλος Αναζήτηση
    Να ξαναγράψετε στο τετράδιό σας τον παραπάνω αλγόριθμο με τα κενά συμπληρωμένα, έτσι ώστε να εμφανίζονται όλες οι θέσεις στις οποίες βρίσκεται ο αριθμός key στον πίνακα table. Ο αλγόριθμος να σταματάει αμέσως μόλις διαπιστωθεί ότι ο αριθμός key δεν υπάρχει στον πίνακα. Εκμεταλλευτείτε το γεγονός ότι τα στοιχεία του πίνακα είναι ταξινομημένα σε αύξουσα σειρά.
  7. (E2013-Α3, ΕΒ2013-Α3) Να γράψετε συμπληρωμένο στο τετράδιό σας το ακόλουθο τμήμα αλγορίθμου, το οποίο πραγματοποιεί αναζήτηση όλων των στοιχείων του πίνακα W[10] στον πίνακα S[1000], έτσι ώστε τα στοιχεία του πίνακα W[10] να καταλαμβάνουν συνεχόμενες θέσεις στον πίνακα S[1000]. Ο αλγόριθμος βρίσκει τη θέση i του S, απ’ όπου αρχίζει η πρώτη εμφάνιση των στοιχείων του W[10]. 
    F ← ΨΕΥΔΗΣ
i ← 1
ΟΣΟ ...... ΚΑΙ ...... ΕΠΑΝΑΛΑΒΕ
   j ← 0
   ΟΣΟ ...... ΚΑΙ ...... ΕΠΑΝΑΛΑΒΕ
      j ← j + 1
   ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
   ΑΝ ...... ΤΟΤΕ
      F ← ΑΛΗΘΗΣ
   ΑΛΛΙΩΣ
      i ← i + 1
   ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΝ F = ΑΛΗΘΗΣ ΤΟΤΕ
   ΓΡΑΨΕ i
ΑΛΛΙΩΣ
   ΓΡΑΨΕ 'ΔΕ ΒΡΕΘΗΚΕ'
ΤΕΛΟΣ_ΑΝ
  8. (E2016-A5) Δίνεται ο πίνακας ΠΙΝ[7] με τις παρακάτω τιμές:
    2 5 8 12 15 17 22
    Και το παρακάτω τμήμα αλγορίθμου: 
    low ← 1
high ← 7
found ← ΨΕΥΔΗΣ
ΟΣΟ low ≤ high ΚΑΙ found=ΨΕΥΔΗΣ επανέλαβε
   mid ← (low+high) DIV 2
   ΕΜΦΑΝΙΣΕ ΠΙΝ[mid]
   ΑΝ ΠΙΝ[mid] < X ΤΟΤΕ low ← mid + 1 ΑΛΛΙΩΣ_ΑΝ ΠΙΝ[mid] > X ΤΟΤΕ
      high ← mid - 1
   ΑΛΛΙΩΣ
      found ← ΑΛΗΘΗΣ
   ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
    Να γράψετε στο τετράδιό σας τις τιμές οι οποίες θα εμφανιστούν για: α) Χ=22 β) Χ=7
  9. Δίνεται ο πίνακας ΠΙΝ[7] με τις παρακάτω τιμές:
    2 5 8 12 15 17 22
    Και το παρακάτω τμήμα αλγορίθμου: low ← 1 high ← 7 found ← ΨΕΥΔΗΣ ΟΣΟ low ≤ high ΚΑΙ found=ΨΕΥΔΗΣ επανέλαβε mid ← (low+high) DIV 2 ΕΜΦΑΝΙΣΕ ΠΙΝ[mid] ΑΝ ΠΙΝ[mid] < 22 ΤΟΤΕ low ← mid + 1 ΑΛΛΙΩΣ_ΑΝ ΠΙΝ[mid] > 22 ΤΟΤΕ high ← mid – 1 ΑΛΛΙΩΣ found ← ΑΛΗΘΗΣ ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ Να γράψετε στο τετράδιό σας τις τιμές οι οποίες θα εμφανιστούν. (E2016-A3)
  10. Δίνεται το παρακάτω τμήμα αλγορίθμου, στο οποίο έχουν αριθμηθεί οι εντολές εκχώρησης και εξόδου.01 ΔΙΑΒΑΣΕ Χ02 ΠΛ ← 003 ΑΡ ← 1 04 ΔΕ ← 12 05 Β ← ΨΕΥΔΗΣ ΌΣΟ Β = ΨΕΥΔΗΣ ΚΑΙ ΑΡ <= ΔΕ ΕΠΑΝΑΛΑΒΕ 06 Μ ← (ΑΡ + ΔΕ) DIV 2       ΑΝ Α[Μ] = Χ ΤΟΤΕ 07 Β ← ΑΛΗΘΗΣ       ΑΛΛΙΩΣ_ΑΝ Α[Μ] < Χ ΤΟΤΕ 08 ΑΡ ← Μ + 1       ΑΛΛΙΩΣ 09 ΔΕ ← Μ – 1       ΤΕΛΟΣ_ΑΝ 10 ΠΛ ← ΠΛ + 1       ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΑΝ Β = ΑΛΗΘΗΣ ΤΟΤΕ 11 ΕΜΦΑΝΙΣΕ Μ       ΑΛΛΙΩΣ 12 ΕΜΦΑΝΙΣΕ “ΔΕΝ ΒΡΕΘΗΚΕ”, ΠΛ       ΤΕΛΟΣ_ΑΝ Για την παρακολούθηση της εκτέλεσης του τμήματος αλγορίθμου με τιμή εισόδου Χ = 35 και με δεδομένο τον πίνακα
    1 2 3 4 5 6 7 8 9 10 11 12
    Α 3 10 18 20 26 32 35 48 55 60 75 90
    δίνεται το παρακάτω υπόδειγμα πίνακα τιμών, συμπληρωμένο ως εξής:
    • Στη στήλη με τίτλο «Αρ. Γρ.» καταγράφεται ο αριθμός γραμμής της εντολής που εκτελείται.
    • Στη στήλη με τίτλο «Έξοδος» καταγράφεται η τιμή εξόδου, εφόσον η εντολή που εκτελείται είναι
    εντολή εξόδου.
    • Οι υπόλοιπες στήλες του πίνακα αντιστοιχούν στις μεταβλητές του τμήματος του αλγορίθμου.
    Αρ. Γρ. Χ ΠΛ ΑΡ ΔΕ Β Μ Έξοδος
    01 35
    02 0
    03 1
    04 12
    05 ΨΕΥΔΗΣ
    … ……..
    Να μεταφέρετε τον πίνακα τιμών στο τετράδιό σας και να προσθέσετε τις γραμμές που χρειάζονται, συνεχίζοντας την εκτέλεση του τμήματος αλγορίθμου ως εξής: για κάθε αριθμημένη εντολή που εκτελείται, να γράψετε τον αριθμό της γραμμής της εντολής σε νέα γραμμή του πίνακα και το αποτέλεσμα της εκτέλεσης της εντολής στην αντίστοιχη στήλη. (Π2016-Β1, Π2016-Β2)
  11. Δίνεται το παρακάτω τμήμα προγράμματος, που υλοποιεί τον αλγόριθμο της σειριακής αναζήτησης της τιμής της μεταβλητής Χ στον πίνακα ονομάτων ON, 100 θέσεων. Το τμήμα περιέχει κενά, τα οποία έχουν αριθμηθεί από [1] έως [5].done <– …[1]…position <– 0i <– …[2]… ΟΣΟ done = ΨΕΥΔΗΣ ΚΑΙ i <= …[3]… ΕΠΑΝΑΛΑΒΕ ΑΝ ON[i] …[4]…X ΤΟΤΕ done <– …[5]… position <– i ΑΛΛΙΩΣ i <– i + 1 ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ Να γράψετε στο τετράδιό σας τους αριθμούς από [1] έως [5] που αντιστοιχούν στα κενά και, δίπλα από κάθε αριθμό, ό,τι πρέπει να συμπληρωθεί, ώστε το τμήμα προγράμματος να υλοποιεί τον αλγόριθμο. (EΞ2016-B1)
  12. Δίνεται μονοδιάστατος πίνακας Π[6] με τις τιμές που φαίνονται παρακάτω.
    1 2 3 4 5 6
    18 29 40 51 62 73
    Για την αναζήτηση μιας τιμής στον πίνακα Π δίνεται το παρακάτω τμήμα αλγορίθμου: Διάβασε X Θέση <– 0 Βρέθηκε <– Ψευδής Υπάρχει <– Αληθής i <– 1 Αρχή_επανάληψης Αν Π[i] = X τότε Βρέθηκε <– Αληθής Θέση <– i Αλλιώς_αν Π[i] > X τότε Υπάρχει <– Ψευδής Τέλος_αν i <– i + 1 Μέχρις_ότου i > 6 ή Βρέθηκε = Αληθής ή Υπάρχει = Ψευδής Να αντιγράψετε στο τετράδιό σας τον πίνακα που δίνεται παρακάτω και να συμπληρώσετε τις τιμές που θα έχουν οι μεταβλητές μετά από την εκτέλεση του τμήματος αλγορίθμου για καθεμία από τις τιμές εισόδου που δίνονται στην πρώτη στήλη.
    Χ Βρέθηκε Υπάρχει i
    10
    40
    70
    100
     (E2017-B2, EΞ2017-B2)
  13. Δίνεται ο παρακάτω αλγόριθμος ο οποίος ελέγχει αν το στοιχείο key βρίσκεται στον πίνακα table[n]τουλάχιστον τρεις (3) φορές και εμφανίζει τη θέση στην οποία βρίσκεται την τρίτη φορά.Αλγόριθμος Β1Δεδομένα // n, table, key // done ← ψευδής position ← 0 i ← 1 count ← …(1)… Όσο i <= …(2)… και done = …(3)… επανάλαβε Αν table[ …(4)… ] = key τότε count ← …(5)… Τέλος_αν Αν count = …(6)… τότε done ← …(7)… …(8)… ← i αλλιώς i ← …(9)… Τέλος_αν Τέλος_επανάληψης Αν …(10)… τότε Εμφάνισε “Το στοιχείο”, key, “υπάρχει τουλάχιστον 3 φορές.” Εμφάνισε “Για τρίτη φορά εμφανίζεται στη θέση “, position, “.” αλλιώς Εμφάνισε “Το στοιχείο”, key, “δεν υπάρχει τουλάχιστον 3 φορές.” Τέλος_αν Τέλος Β1 Να γράψετε στο τετράδιό σας τους αριθμούς των κενών και δίπλα ό,τι χρειάζεται να συμπληρωθεί έτσι ώστε ο αλγόριθμος να λειτουργεί σωστά. (Ε2019-Β1, Β2019-Β1)
  14. Το παρακάτω τμήμα προγράμματος σειριακής αναζήτησης σε πίνακα table[n] έχει πέντε (5) λάθη. Ναεντοπίσετε τις εντολές που περιέχουν λάθη και να γράψετε στο τετράδιό σας τον αριθμό (080 – 180)καθεμιάς λανθασμένης εντολής και δίπλα διορθωμένη την αντίστοιχη εντολή.080  done ← ψευδής 090  i ← 1 100  Όσο (done = ψευδής) ΚΑΙ (i>n) επανάλαβε 110      Αν table[1]=key τότε 120          done ← ‘αληθής’ 130          position ← i 140      αλλιώς 150          i ← i + 2 160      Τέλος_επανάληψης 170  Τέλος_επανάληψης 180  Γράψε position (B2019-B2)