.. py:module:: cercadic

Cerca dicotòmica
================

Un algorisme molt important en informàtica és la `cerca
dicotòmica <https://en.wikipedia.org/wiki/Binary_search>`__, 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.

#. 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
   :file:`cercadic.py` (mòdul :py:mod:`cercadic`):

   .. py:function:: es_en_llista(llista, elem)

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

   Per exemple:

   .. literalinclude:: es_en_llista.txt
       :language: python
       :lines: 2-8

   .. note::

      Disposeu de jocs de prova al fitxer :download:`es_en_llista.txt`.


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

   .. py:function:: 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:

   .. literalinclude:: index_llista.txt
       :language: python
       :lines: 2-8

   .. note::

      Disposeu de jocs de prova al fitxer :download:`index_llista.txt`.

.. rubric:: Solució

Disposeu de solucions al fitxer :download:`cercadic.py
<solucio/cercadic.py>`.