12. Algoritmos de búsqueda

(★☆☆, ★★☆, ★★★) Esta notación indica la dificultad de cada ejercicio, de menor a mayor.

1. ★☆☆ Implementar una función que tome una lista de números y un número y devuelva la posición de la primera aparición de ese número en la lista. Si el número no está en la lista debe devolver -1.

2. ★☆☆ Implementar una función que tome una lista de números y un número y devuelva la posición de la última aparición de ese número en la lista. Si el número no está en la lista debe devolver -1.

3. ★☆☆ Implementar una función que tome una lista de números ordenada de menor a mayor y un número y devuelva la posición de alguna aparición de ese número en la lista. Si el número no está en la lista debe devolver -1. La busqueda debe ser eficiente, es decir, no debe recorrer toda la lista si no es necesario.

4. ★★★ Se tiene una lista que contiene diccionarios con las claves “id”, “descripcion”, “costo” y “stock”. Un ejemplo de listas de este tipo es el siguiente:

   [{"id": 4, "descripcion": "Girgola", "costo": 449.0, "stock": 324},
   {"id": 2, "descripcion": "Espinaca", "costo": 799.0, "stock": 3501},
   {"id": 3, "descripcion": "Champignon", "costo": 629.0, "stock": 723},
   {"id": 12, "descripcion": "Kiwi", "costo": 1299.0, "stock": 150},
   {"id": 10, "descripcion": "Mandarina Okitsu", "costo": 389.0, "stock": 430},
   {"id": 11, "descripcion": "Mandarina Nova", "costo": 389.0, "stock": 900}]
   

   • Implementar una función que tome una lista con este formato y un id y devuelva el diccionario de la lista que contenga el id especificado.
   • Implementar una función que tome una lista con este formato y una descripción y devuelva el stock del elemento cuya descripción coincide con la especificada.

5. ★★★ Se tiene la misma lista que en el ejercicio anterior pero ordenada por id:

   [{"id": 2, "descripcion": "Espinaca", "costo": 799.0, "stock": 3501},
   {"id": 3, "descripcion": "Champignon", "costo": 629.0, "stock": 723},
   {"id": 4, "descripcion": "Girgola", "costo": 449.0, "stock": 324},
   {"id": 10, "descripcion": "Mandarina Okitsu", "costo": 389.0, "stock": 430},
   {"id": 11, "descripcion": "Mandarina Nova", "costo": 389.0, "stock": 900},
   {"id": 12, "descripcion": "Kiwi", "costo": 1299.0, "stock": 150}]
   

   • Implementar una función que dada una descripcion de un producto y una cantidad a comprar nos devuelva si hay stock suficiente para poder realizar esa compra.
   • Implementar una función que dado un id de un producto nos devuelva su precio, siendo el precio igual al costo + 20%. El peor caso de la función debe resolverse en un tiempo mejor que \(\mathcal{O}(n)\), donde \(n\) es la cantidad de elementos en la lista.

6. ★★★ Se tiene una lista que contiene diccionarios con las claves “nombre”, “mesa”, y “especial”. Un ejemplo de listas de este tipo es el siguiente:

   [{"nombre": "Gabi", "mesa": 3, "especial": "si"},
   {"nombre": "Dani", "mesa": 1, "especial": "no"},
   {"nombre": "Aike", "mesa": 3, "especial": "si"},
   {"nombre": "Pato", "mesa": 1, "especial": "si"},
   {"nombre": "Indigo", "mesa": 1, "especial": "si"},
   {"nombre": "Sora", "mesa": 2, "especial": "si"},
   {"nombre": "Cris", "mesa": 2, "especial": "no"},
   {"nombre": "Matu", "mesa": 3, "especial": "no"},
   {"nombre": "Alex", "mesa": 1, "especial": "no"},
   {"nombre": "Xue", "mesa": 2, "especial": "no"},
   {"nombre": "Ariel", "mesa": 2, "especial": "no"}]
   

   • Implementar una función que tome una lista con este formato y un nombre y devuelva la mesa en la que se encuentra la persona con ese nombre.

7. ★★★ Se tiene la misma lista que en el ejercicio anterior pero ordenada por nombre:

   [{'nombre': 'Aike', 'mesa': 3, 'especial': 'si'},
   {'nombre': 'Alex', 'mesa': 1, 'especial': 'no'},
   {'nombre': 'Ariel', 'mesa': 2, 'especial': 'no'},
   {'nombre': 'Cris', 'mesa': 2, 'especial': 'no'},
   {'nombre': 'Dani', 'mesa': 1, 'especial': 'no'},
   {'nombre': 'Gabi', 'mesa': 3, 'especial': 'si'},
   {'nombre': 'Indigo', 'mesa': 1, 'especial': 'si'},
   {'nombre': 'Matu', 'mesa': 3, 'especial': 'no'},
   {'nombre': 'Pato', 'mesa': 1, 'especial': 'si'},
   {'nombre': 'Sora', 'mesa': 2, 'especial': 'si'},
   {'nombre': 'Xue', 'mesa': 2, 'especial': 'no'}]
   

   • Implementar una función que tome una lista con este formato y un nombre y devuelva la mesa en la que se encuentra la persona con ese nombre.
   • El peor caso de la función debe resolverse en un tiempo mejor que \(\mathcal{O}(n)\), donde \(n\) es la cantidad de elementos en la lista.