Searching Algorithms


Ternary Search

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

Η τριαδική αναζήτηση ανήκει στην κατηγορία «διαίρει και βασίλευε» και μπορεί πολύ εύκολα να γενικευτεί σε k-αδική αναζήτηση χωρίζοντας το σύνολο σε k υποσύνολα. Η πολυπλοκότητα είναι λογαριθμική και ανάλογη προς το μέγεθος της εισόδου με βάση του λογαρίθμου το k. Στη συγκεκριμένη περίπτωση παρόλο που σε κάθε επανάληψη απορρίπτονται τα δύο τρίτα της λίστας, η τριαδική αναζήτηση δεν είναι πιο αποδοτική από τη δυαδική. Αυτό συμβαίνει διότι σε κάθε βήμα γίνονται δύο συγκρίσεις έναντι μίας στη δυαδική με αποτέλεσμα συγκρίσεις οι οποίες είναι περισσότερες από τις .

Pseudocode

 1.TernarySearch(A[0..N-1], value)
 2.
left ← 0

 3.
right ← N – 1

 4.
while (left ≤ right)

 5.
leftThird ← left +

 6.
rightThird ← right -

 7.
if (Α[leftThird] = value)

 8.
return leftThird

 9.
else if (A[rightThird] = value)

10.
return rightThird

11.
else if (A[leftThird] > value)

12.
right ← (leftThird – 1)

13.
else if (A[rightThird] < value)

14.
left ← (rightThird + 1)

15.
else

16.
left ← (leftThird + 1)

17.
right ← (rightThird - 1)

18.
end if

19.
end while

20.
return -1

21.end

Applet

Java applet that demonstrates ternary search algorithm.

Example

Έστω ο πίνακας A=[1 2 3 4 5 6 7 8 9 10], και value=9 το ζητούμενο στοιχείο. Υπολογίζουμε τα left και right με τιμές 0 και 9 αντίχτοιχα. Επειδή 0 ≤ 9 εκτελούνται οι εντολές του βρόχου while.

leftThird , rightThird

Υπολογίζουμε τα Α[leftThird] και Α[rightThird] και εξετάζουμε αν ισχύει κάποια από τις συνθήκες ελέγχου if.

A[3]=4, 4≠9
A[6]=7, 7≠9
A[3]=4, 4≤9
A[6]=7, 7<9, left=7

Παρατηρούμε ότι ισχύει η 4η συνθήκη και υπολογίζουμε τη νέα τιμή του left. Η συνθήκη left ≤ right είναι αληθής (7 ≤ 9) και επαναλαμβάνεται η προηγούμενη διαδικασία δίνοντας τα παρακάτω αποτελέσματα.

leftThird , rightThird
A[7]=8, 8≠9
A[9]=10, 10≠9
A[7]=8, 8<=9
A[9]=10, 10>=9
left=8, right=8

Αυτή τη φορά δεν ικανοποιήθηκε καμία από τις συνθήκες ελέγχου με αποτέλεσμα να αλλάξουν τιμή και οι δύο μεταβλητές. Οι εντολές του βρόχου while θα εκτελεστούν για μία ακόμη φορά (8 ≤ 8) και θα καταλήξουμε στο επιθυμητό αποτέλεσμα.

leftThird , rightThird
A[8]=9, 9=9