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

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

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

[55, 46, 44, 34, 28, 18, 14, 12, 10, 8, 4]

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

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

Τι θα συμβεί στο παρακάτω τμήμα αλγορίθμου;

students = ['Δημήτρης', 'Ευγενία', 'Ναταλία', 'Ρένια', 'Αλέξανδρος']

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]

Στην παρακάτω αύξουσα ταξινομημένη λίστα  L ψάχνουμε το 45.

η πρώτη σύγκριση για τον αριθμό 45 θα είναι με το στοιχείο στο δείκτη: (0+13)/2 =6 άρα με τον L[6] άρα με το 35.

επειδή 45>35 θα ελέγξει από το δείκτη 6+1 = 7 έως το τέλος της λίστας.

Άρα ο επόμενος έλεγχος θα είναι με το στοιχείο στο δείκτη: (7 + 13) / 2 = 10, άρα με το 60

Με ποιο στοιχείο θα ελεγχθεί μετά;

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

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

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

Η αντιμετάθεση (αμοιβαία αλλαγή τιμών των μεταβλητών α, β) γίνεται στην Pyhton με την απλή εντολή:

a, b = b, a

Πως μπορεί να γίνει με επιπλέον μεταβλητή;

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

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

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

Η παρακάτω συνάρτηση υπολογίζει σωστά το πλήθος των 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)

Να επιλεξετε τον  σωστό αλγόριθμο της Δυαδικής αναζήτησης ενός στοιχείου key σε μια αύξουσα ταξινομημένη λίστα array

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

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] χρησιμοποιώντας τη βελτιστοποιημένη ταξινόμηση και πόσα άσκοπα θα γινόταν με τον απλό αλγόριθμο ταξινόμησης;

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

Σε μια ταξινομημένη λίστα 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 'Δυστυχώς δεν το βρήκες'

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

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

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

για την παρακάτω λίστα a=[9, -2, 6, 4, -8, 12, 5, 18] Συμπληρώστε τα κενά για να γίνει αύξουσα ταξινόμηση

a = [9, -2, 6, 4, -8, 12, 5, 18]

N = len(a)

for i in range(N-1):

        for j in range( ___  ,  _____ , -1):

                if a[j+1] > a[j]:

                       a[j], a[j + 1] = a[j + 1], a[j]