Búsqueda Lineal - dambort/algos GitHub Wiki

Problema: dado un vector V de n elementos ordenado, escriba una función para buscar un elemento dado x en el vector V.

Ejemplos:

  1. 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

  2. Si V[ ] = {1, 2, 5, 3, 8, 7, 10} x = 9;
    Salida: -1, ya que el elemento x no está presente en V[ ]

Idea del algoritmo:

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.

Código

Disponible en Enciclopedia Algoritmos C++

Ejemplo de uso

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.

En Ideone

Ver código y ejecución en línea en Búsqueda Lineal en Ideone

Problemas en sitios jueces que se pueden resolver con búsqueda lineal de un elemento en un vector.

  • 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