Ejercicios del Capítulo 15
     Volver al índice.
     

     
     Asumiendo que nuestro programa realiza una búsqueda lineal, reponde a lo siguiente:
     
  1. Si una lista tiene n elementos, ¿cuántos de ellos debería comprobar el ordenador, en el mejor de los casos, para encontrar el deseado?

  2. Si una lista tiene n elementos, ¿cuántos de ellos debería comprobar el ordenador, en el peor de los casos, para encontrar el deseado?

  3. Si una lista tiene n elementos, ¿cuántos de ellos deberíamos comprobar para poder saber que el elemento deseado no existe en la lista?

  4. Si una lista tiene n elementos, ¿cuántos de ellos como media, debería comprobar el ordenador para encontrar el deseado?

  5. (2 pts) Toma el código del ejemplo de búsqueda lineal e introdúcelo en una función llamada
     busqueda_lineal. Toma como parámetros la lista y el elemento buscado. Devuelve la
     posición del elemento o -1 si no lo encuentra. Recuerda, DEVUELVE (Return) el valor. Si tu
     función tiene una declaración que use print, lo estás haciendo mal. Una vez que hayas escrito
     la función, pruébala a ver si funciona con el siguiente código:

     
     # --- Coloca debajo tu definición de busqueda_lineal:

     # --- Bien, si la función es correcta, los siguientes tests deberían funcionar:

     mi_lista = [4, 3, 2, 1, 5, 7, 6]

     r = busqueda_lineal(mi_lista, 3)
     if r == 1:
         print("Test A bien")
     else:
         print("Test A mal. Esperaba 1 y obtuvimos", r)

     r = busqueda_lineal(mi_lista, 2)
     if r == 2:
         print("Test B bien")
     else:
         print("Test B mal. Esperaba 1 y obtuvimos", r)

     r = busqueda_lineal(mi_lista, 10)
     if r == -1:
         print("Test C bien")
     else:
         print("Test C mal. Esperaba -1 y obtuvimos", r)
     
     

     

     Asumiendo que nuestro programa realiza una búsqueda binaria, y que la lista de búsqueda está ordenada, reponde a lo siguiente:
     
  6. Si una lista tiene n elementos, ¿cuántos de ellos debería comprobar el ordenador, en el mejor de los casos, para encontrar el deseado?

  7. Si una lista tiene n elementos, ¿cuántos de ellos debería comprobar el ordenador, en el peor de los casos, para encontrar el deseado?

  8. Si una lista tiene n elementos, ¿cuántos de ellos deberíamos comprobar para poder saber que el elemento deseado no existe en la lista?

  9. Si una lista tiene n elementos, ¿cuántos de ellos como media, debería comprobar el ordenador para encontrar el deseado?

 10. (2 pts) Toma el código del ejemplo de búsqueda binaria e introdúcelo en una función llamada
     busqueda_binaria. Toma como parámetros la lista y el elemento buscado. Devuelve la
     posición del elemento, o -1 si no lo encuentra. Una vez que hayas escrito la función,
     pruébala a ver si funciona con el siguiente código:

     
     mi_lista = [0, 3, 5, 12, 18, 50, 70, 78]

     r = busqueda_binaria(mi_lista, 3)
     if r == 1:
         print("Test A bien")
     else:
         print("Test A mal. Esperaba 1 y obtuvimos", r)

     r = busqueda_binaria(mi_lista, 5)
     if r == 2:
         print("Test B bien")
     else:
         print("Test B mal. Esperaba 2 y obtuvimos", r)

     r = busqueda_binaria(mi_lista, 10)
     if r == -1:
         print("Test C bien")
     else:
         print("Test C mal. Esperaba -1 y obtuvimos", r)
     

     
 11. ¿Es posible que la siguiente función sea capaz de determinar correctamente
     si una lista contiene al menos un elemento positivo? Escribe el código para
     comprobarlo.Explica por qué crees que funciona o por qué no funciona.(1 punto).
     Escribe el código necesario para que funcione (1 punto.)
     
     def detectar_positivo(mi_lista):
         for elemento in mi_lista:
             if elemento > 0:
                 return True
             else:
                 return False