Μάθημα : Προγραμματισμός Η/Υ

Αλγόριθμος Δυαδικής αναζήτησης
Προσοχή ο αλγόριθμος λειτουργεί σε ταξινομημένα δεδομένα
#1η συνάρτηση
συνάρτηση που επιστρέφει True όταν το στοιχείο υπάρχει στη λίστα διαφορετικα επιστρέφει False

def binarySearch(lista,kleidi):
                  proto=0
                  teleytaio=len(lista)-1
                  vrethike= False
                  while proto<=teleytaio and not vrethike :
                                         mesaio=(proto+teleytaio) / 2
                                         if lista[mesaio]==kleidi:
                                                        vrethike= True
                                         elif lista[mesaio]<kleidi:
                                                        proto= mesaio+1
                                         else :
                                                  teleytaio = mesaio-1
                  return vrethike

#2η συνάρτηση
συνάρτηση που επιστρέφει τη θέση που βρίσκεται το στοιχείο στη λίστα διαφορετικα επιστρέφει -1

def binarySearchThesi(lista,kleidi):
                  proto=0
                  teleytaio=len(lista)-1
                  thesi=-1
                  while proto<=teleytaio and thesi==-1 :
                                     mesaio=(proto+teleytaio) / 2
                                     if lista[mesaio]==kleidi:
                                                  thesi= mesaio
                                     elif lista[mesaio]<kleidi:
                                                 proto= mesaio+1
                                     else :
                                                  teleytaio = mesaio-1
                return thesi   

Παράδειγμα

def binarySearchThesi(lista,kleidi):
    proto=0
    teleytaio=len(lista)-1
    thesi=-1
    while proto<=teleytaio and thesi==-1 :
        mesaio=(proto+teleytaio) / 2
        if lista[mesaio]==kleidi:
            thesi= mesaio
        elif lista[mesaio]<kleidi:
            proto= mesaio+1
        else :
            teleytaio = mesaio-1
    return thesi
#-----------------------------------------------------------------
a=range(1,100,7) #δημιουργια της λιστας
ar=input('dose arithmo ')
print 'Thesi ', binarySearchThesi(a,ar)
print a

B2.
Δίνεται παρακάτω η λίστα Α.

Να γράψετε στο τετράδιό σας τους αριθμούς της λίστας που θα συγκριθούν κατά την εκτέλεση του αλγορίθμου της δυαδικής αναζήτησης σε κάθε μία από τις παρακάτω περιπτώσεις:
α) για τον αριθμό 100 (μον. 4)
β) για τον αριθμό 1 (μον. 3)
Μονάδες 7
(ΠΑΝΕΛΛΑΔΙΚΕΣ ΕΞΕΤΑΣΕΙΣ ΙΟΥΝΙΟΥ 2018)

Β1.
Δίνεται ο παρακάτω αλγόριθμος της δυαδικής αναζήτησης που εφαρμόζεται σε λίστα, της οποίας τα στοιχεία είναι διατεταγμένα σε φθίνουσα σειρά.
def binarySearch(array, key):
                  first = 0
                  last = (1)
                  pos = -1
                  while first <= (2) and pos == (3) :
                             mid = (first + last)/2
                             if array[mid] == key:
                                           (4) = mid
                             elif array[mid] < key:
                                           (5) = mid – 1
                             else:
                                           (6) = (7)
                   return (8)
Στο τμήμα προγράμματος υπάρχουν οκτώ (8) κενά, τα οποία έχουν αριθμηθεί και υπογραμμιστεί. Να γράψετε στο τετράδιό σας τον αριθμό του κενού και δίπλα τι πρέπει να συμπληρωθεί, ώστε το τμήμα προγράμματος να εκτελεί σωστά τη λειτουργία του.
Μονάδες 8
(ΠΑΝΕΛΛΑΔΙΚΕΣ ΕΞΕΤΑΣΕΙΣ ΙΟΥΝΙΟΥ 2020)

import random
def binarySearchThesi(lista,kleidi):
          proto=0
          teleytaio=len(lista)-1
          thesi=-1
          while proto<=teleytaio and thesi==-1 :
                     mesaio=(proto+teleytaio) / 2
                     if lista[mesaio]==kleidi:
                                thesi= mesaio
                    elif lista[mesaio]<kleidi:
                                proto= mesaio+1
                   else :
                                 teleytaio = mesaio-1
          return thesi
def bubbleSort(A):
       N=len(A)
        for i in range(N-1):#καθορίζει πόσα "περάσματα" θα γίνουν
                  for j in range(N-1, i, -1):
                               if A[ j ] < A[ j-1 ] :
                                            A[ j ], A[ j-1 ] = A[ j-1 ], A[ j ]
#Κυριως προγραμμα
lista=[]#αρχικοποιήση
for i in range(200):
                               lista+=[random.randint(1000,9999)]
                                #προσθετει ένα τυχαιο αριθμο στη λιστα
print lista
print 'Taxinomimei'
bubbleSort(lista)
print lista
psahno=input ('ποιον αριθμό ψάχνεις ')
if binarySearchThesi(lista,psahno)!=-1:
                         print 'θεση:',binarySearchThesi(lista,psahno)
else:
                         print 'δεν υπαρχει!!!!'