Búsqueda Lineal
Problema: dado un vector V de n elementos ordenado, escriba una función para buscar un elemento dado x en el vector V.
Ejemplos:
-
Si V[ ] = {1, 2, 5, 3, 8, 7, 10}
x = 8;
Salida: 4, ya que el elemento x está presente en la posición 4 -
Si V[ ] = {1, 2, 5, 3, 8, 7, 10} x = 9;
Salida: -1, ya que el elemento x no está presente en V[ ]
Se recorre el vector desde el elemento de la izquierda de V[ ] hacia la derecha, comparando cada elemento con x. Si se lo encuentra se retorna la posición de x. Si se llega al final del vector y no se lo encontró, se retorna -1, como valor que indica que x no se encuentra en el vector.
Disponible en Enciclopedia Algoritmos C++
Disponible en ejemplo búsqueda lineal
Complejidad: O(n), en el peor caso posible, el elemento buscado no se encuentra en el vector, y eso implica recorrer el vector de forma completa.
Ver código y ejecución en línea en Búsqueda Lineal en Ideone
- Conocés alguno que se pueda nombrar acá ??? Avisános!!!
Colaborador autor del artículo: Daniel Ambort
Fecha última modificación: 2 de octubre de 2019
Algos - Proyecto Iniciado por la cátedra "Algoritmos y Estructuras de Datos" en Agosto de 2019 - UTN Santa Fe - Argentina.
Objetivo: Elaborar una enciclopedia de algoritmos codificados en C++, que resuelvan problemas habitualmente tratados en las asignaturas de Fundamentos de Programación, como herramienta complementaria al proceso de aprendizaje de los alumnos de la asignatura, y de los entusiastas de programación y de las competencias de programación como TecnoMate.