Η δυαδική αναζήτηση μπορεί να γίνει σε στοιχεία που βρίσκονται σε κάποια λογική διάταξη, είτε αυτά είναι αριθμοί είτε αλφαριθμητικά

Η δυαδική αναζήτηση μπορεί να χρησιμοποιηθεί τόσο σε αύξουσα ταξινομημένη λίστα, όσο και σε φθίνουσα

Πόσα περάσματα θα γίνουν για την αύξηση ταξινόμηση της λίστας:

[4, 6, 8, 18, 30, 50, 56, 68, 70, 3, 1]

Ο παρακάτω αλγόριθμος επιλέγει έναν αριθμό από το 1 έως και το 100 και ο χρήστης προσπαθεί να τον μαντέψει. Βελτιώστε τον αλγόριθμο στην  else:  ώστε το πρόγραμμα να δίνει μια βοήθεια στο χρήστη, ώστε αν ο αριθμός που έδωσε είναι μικρότερος ή μεγαλύτερος να εμφανίζεται αντίστοιχο μήνυμα

import random

secret_number = random.randint(1, 100)  # ο αριθμός που επιλέγει τυχαίο ο Η/Υ

guesses = 0   #προσπάθειες

found = False

while not found:

        guess = input(' Μάντεψε τον αριθμό')  # Ο αριθμός που δίνει ο χρήστης

        guesses + = 1

        if guess == secret_number:

                print 'Μπράβο το βρήκες με', guesses, 'προσπάθειες'

                found = True

        else:

                print 'Δυστυχώς δεν το βρήκες, ξαναπροσπάθησε'
 

Πόσα περάσματα θα γίνουν για την αύξηση ταξινόμηση της λίστας:

[28, 28, 28, 6, 6, 6, 6, 6, 6, 6, 6]

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

def binarySearch(lista, key):

        first = 0

        last = len(lista) - 1

        found = False

        while not found and first <= last:

                mid = (first + last) / 2

                if lista[mid] == key:

                      found = True

                elif lista[mid] < key:

                      first = mid + 1

                else:

                     last = mid - 1

        return found

Δίνεται το πρόβλημα: Να βρεθούν οι τρεις μεγαλύτεροι αριθμοί σε μια λίστα

Τι λύση θα επιλέγατε;

Επιλέξτε έναν πιο συνοπτικό τρόπο εκτέλεσης των παρακάτω εντολών, που δηλώνουν το πρώτο πέρασμα της αύξουσας ταξινόμησης σε μια λίστα 5 στοιχείων:

if students[4] < students[3]:

        students[4], students[3] = students[3], students[4]

if students[3] < students[2]:

        students[3], students[2] = students[2], students[3]

if students[2] < students[1]:

        students[2], students[1] = students[1], students[2]

if students[1] < students[0]:

        students[1], students[0] = students[0], students[1]

Για την παρακάρω λίστα με 7 αριθμούς ποια θα είναι η τιμή της λίστας μετά από τρία περάσματα, αν χρησιμοποιήσουμε τον αλγόριθμο της αύξουσας ταξινόμησης (φυσαλίδα);

[55, 34, 5, 3, 2, 1, 1]

Η παρακάτω συνάρτηση υπολογίζει σωστά το πλήθος των True σε μια λίστα; Τι θα εμφανίσει το πρόγραμμα;

def count_True(lista):

        pl_true=0

        for item in lista:

                if item:

                        pl_true + = item

        return pl_true

L = [True, True, True, False, False]

print count_True(L)

Η σειριακή αναζήτηση σαρώνει όλα τα στοιχεία μιας ταξινομημένης λίστας χωρίς να εκμεταλλεύεται τη διάταξη των στοιχείων

Ο παρακάτω αλγόριθμος βελτιστοποιεί την ταξινόμηση, ώστε όταν η λίστα ταξινομηθεί να μην κάνει άσκοπα περάσματα

def optimizedBubbleSort(A):

        N = len(A)

        isSorted = False

        i = 0

       while i < N-1  and not isSorted:

                isSorted = True

                for j in range(N-1, i, -1):

                        if A[j] < A[j-1]:

                               A[j], A[j-1] = A[j-1], A[j]

                               isSorted = False

                i + = 1

πόσα περάσματα θα γίνουν για τη λίστα [7, 8, 9, 12, 4, 5, 11] χρησιμοποιώντας τη βελτιστοποιημένη ταξινόμηση και πόσα άσκοπα θα γινόταν με τον απλό αλγόριθμο ταξινόμησης;

Τι θα εμφανίσει το παρακάτω πρόγραμμα;

 def isAscending(mylist):

        ascending = True

        i = 0

        N = len(mylist)

        while ascending and i < N-1:

                if myList[i] > myList[i + 1]:

                        ascending = False

                i = i + 1

        return ascending

L = [12, 40, 58, 80, 79]

print isAscending(L)

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

def binarySearch(lista, key):

        first = 0

        last = len(lista) - 1

        found = False

        while not found and first <= last:

                mid = (first + last) / 2

                if lista[mid] == key:

                      found = True

                elif lista[mid] > key:

                      first = mid + 1

                else:

                     last = mid - 1

        return found

Ο αλγόριθμος της Σειριακή αναζήτησης θα ελέγξει όλα τα στοιχεία σε μια λίστα ακόμα και αν είναι ταξινομημένη

Πόσα περάσματα θα γίνουν για την αύξηση ταξινόμηση της λίστας:

[28, 28, 28, 28, 28, 28, 28, 30, 30, 30, 30]

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

def binarySearch(lista, key):

        first = 0

        last = len(lista) - 1

        found = False

        while not found and first <= last:

                mid = (first + last) / 2

                if  key == lista[mid] :

                      found = True

                elif key <lista[mid]  :

                      last = mid - 1

                else:

                    first  = mid +1

        return found

Σε μια ταξινομημένη λίστα 100 στοιχείων, πόσες είναι οι περισσότερες συγκρίσεις που θα χρειαζόταν για να βρεθεί οποιοδήποτε στοιχείο χρησιμοποιοώντας τη δυαδική αναζήτηση;

Ο παρακάτω αλγόριθμος επιλέγει έναν αριθμό από το 1 έως και το 1000 και ο χρήστης προσπαθεί να τον μαντέψει με τη βοήθεια μηνυμάτων από το Η/Υ (αν ο αριθμός που έδωσε ο χρήστης είναι μικρότερος ή μεγαλύτερος). Βελτιώστε τον αλγόριθμο στην  while ώστε ο χρήστης να σκεφτεί με καλύτερη στρατηγική και να μειώσει τις προσπάθειές του για να βρει τον κρυφό αριθμό. Οι προσπάθειες που θα μπορεί να δώσει είναι 10

import random

secret_number = random.randint(1, 1000)  # ο αριθμός που επιλέγει τυχαίο ο Η/Υ

guesses = 0   #προσπάθειες

found = False

while not found:

        guess = input(' Μάντεψε τον αριθμό')  # Ο αριθμός που δίνει ο χρήστης

        guesses + = 1

        if guess == secret_number:

                print 'Μπράβο το βρήκες με', guesses, 'προσπάθειες'

                found = True

        else:

                if guess < secrtet_number:

                        print ' Ο αριθμός σου είναι μικρότερος από τον ζητούμενο'

                else:

                        print ' Ο αριθμός σου είναι μεγαλύτερος από τον ζητούμενο'  

#Τέλος της while

if  found :  # αφού αν είναι True αρκεί (μπορούμε και found == True:)

        print 'Μπράβο το βρήκες με ', guesses, ' προσπάθειες'

else:

        print 'Δυστυχώς δεν το βρήκες'

O παρακάτω αλγόριθμος της αύξουσας ταξινόμησης Ν στοιχείων σε τι μειονεκτεί;

for i in range(N-1):

        for j in range(N-1, 0, -1):

                if A[j] < A[j-1]:

                       A[j], A[j-1] = A[j-1], A[j]