Cerca dicotòmica

Un algorisme molt important en informàtica és la cerca dicotòmica, també anomenada cerca binària. Es tracta d’un mètode que només és aplicable a conjunts ordenats amb accés directe als components. A cada pas, l’algorisme compara l’element buscat amb l’element central de la seqüència (el del mig). Si coincideixen, llavors la cerca ha acabat amb èxit. Altrament, si l’element buscat és més petit que el central, es repeteix la cerca en la subseqüència de la part esquerra de l’element central; i si l’element cercat és més gran que l’element central, només caldrà cercar en la subseqüència de la dreta. Quan la seqüència en la qual cal cercar és buida, el procés s’acaba sense èxit.

1. Utilitzant la recursivitat, dissenyeu la funció següent, que ha d’usar el mètode de la cerca dicotòmica. Deseu-la en el fitxer cercadic.py (mòdul cercadic):

   cercadic.es_en_llista(llista, elem)

   Donada una llista ordenada, retorna True si l’element és a la llista i False altrament.

   Per exemple:

   >>> l1 = [2, 5, 7, 15, 19, 23, 25, 28, 31, 33, 36, 37, 42, 45, 48]
   >>> es_en_llista(l1, 28)
   True
   >>> es_en_llista(l1, 1)
   False
   >>> es_en_llista(l1, 7)
   True
   

   Nota

   Disposeu de jocs de prova al fitxer es_en_llista.txt.

2. Utilitzant la recursivitat, dissenyeu la funció següent i deseu-la en el fitxer cercadic.py (mòdul cercadic):

   cercadic.index_llista(llista, elem)

   Donada una llista ordenada, retorna l’índex corresponent a la posició de l’element a la llista. Si l’element no és a la llista, retorna -1.

   Per exemple:

   >>> l1 = [2, 5, 7, 15, 19, 23, 25, 28, 31, 33, 36, 37, 42, 45, 48]
   >>> index_llista(l1, 28)
   7
   >>> index_llista(l1, 1)
   -1
   >>> index_llista(l1, 7)
   2
   

   Nota

   Disposeu de jocs de prova al fitxer index_llista.txt.

Solució

Disposeu de solucions al fitxer cercadic.py.