1511 - FCautareRec

Cerinţa

Scrieţi definiția completă a unei funcții recursive care are ca parametrii un număr natural n, un șir crescător X de numere reale având n elemente și un număr real v și care returnează poziția pe care apare în șir valoarea v. În cazul în care v nu apare în șir, se va returna valoarea -1. În cazul în care v apare în șir pe mai multe poziții, se va returna una dintre acestea.

Date de intrare

Se va introduce de la tastatură un număr natural care va fi transmis ca perimetru

Date de ieșire

Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse." În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse.".

Restricţii şi precizări

0 < n <= 100 v și elementele lui X sunt numere reale – se va folosi tipul double numele subprogramului cerut este cautare parametrii sunt, în această ordine: n, X, v elementele tabloului X sunt indexate de la zero se recomandă realizarea unei soluții recursive

Exemplu

Dacă n=6, X=(9.5,16.3,28.3,49.7,52.4,73), iar v=52.4, funcția va returna valoarea 4.

Important

Soluţia propusă va conţine doar definiţia subprogramului cerut. Prezenţa în soluţie a altor instrucţiuni poate duce erori de compilare sau de execuţie care vor avea ca efect depunctarea soluţiei.

Rezolvare

def cautare(n, X, v):
   # verificare dacă v se află între capetele șirului
   if v < X[0] or v > X[n-1]:
       return -1
   
   # calculăm mijlocul șirului
   mijloc = int((n-1)/2)
   
   # dacă valoarea v se află în mijlocul șirului, returnăm poziția
   if v == X[mijloc]:
       return mijloc
   
   # dacă v este mai mic decât mijlocul, căutăm recursiv în jumătatea stângă a șirului
   elif v < X[mijloc]:
       return cautare(mijloc, X[:mijloc], v)
   
   # dacă v este mai mare decât mijlocul, căutăm recursiv în jumătatea dreaptă a șirului
   else:
       return cautare(n - mijloc - 1, X[mijloc+1:], v) if n-mijloc-1>0 else -1