The Algorithms logo
The Algorithms
Acerca deDonar

Linear Search

A
J
E
E
L
Y 45 más contribuidores
"""
This is pure Python implementation of linear search algorithm

For doctests run following command:
python3 -m doctest -v linear_search.py

For manual testing run:
python3 linear_search.py
"""


def linear_search(sequence: list, target: int) -> int:
    """A pure Python implementation of a linear search algorithm

    :param sequence: a collection with comparable items (as sorted items not required
        in Linear Search)
    :param target: item value to search
    :return: index of found item or None if item is not found

    Examples:
    >>> linear_search([0, 5, 7, 10, 15], 0)
    0
    >>> linear_search([0, 5, 7, 10, 15], 15)
    4
    >>> linear_search([0, 5, 7, 10, 15], 5)
    1
    >>> linear_search([0, 5, 7, 10, 15], 6)
    -1
    """
    for index, item in enumerate(sequence):
        if item == target:
            return index
    return -1


def rec_linear_search(sequence: list, low: int, high: int, target: int) -> int:
    """
    A pure Python implementation of a recursive linear search algorithm

    :param sequence: a collection with comparable items (as sorted items not required
        in Linear Search)
    :param low: Lower bound of the array
    :param high: Higher bound of the array
    :param target: The element to be found
    :return: Index of the key or -1 if key not found

    Examples:
    >>> rec_linear_search([0, 30, 500, 100, 700], 0, 4, 0)
    0
    >>> rec_linear_search([0, 30, 500, 100, 700], 0, 4, 700)
    4
    >>> rec_linear_search([0, 30, 500, 100, 700], 0, 4, 30)
    1
    >>> rec_linear_search([0, 30, 500, 100, 700], 0, 4, -6)
    -1
    """
    if not (0 <= high < len(sequence) and 0 <= low < len(sequence)):
        raise Exception("Invalid upper or lower bound!")
    if high < low:
        return -1
    if sequence[low] == target:
        return low
    if sequence[high] == target:
        return high
    return rec_linear_search(sequence, low + 1, high - 1, target)


if __name__ == "__main__":
    user_input = input("Enter numbers separated by comma:\n").strip()
    sequence = [int(item.strip()) for item in user_input.split(",")]

    target = int(input("Enter a single number to be found in the list:\n").strip())
    result = linear_search(sequence, target)
    if result != -1:
        print(f"linear_search({sequence}, {target}) = {result}")
    else:
        print(f"{target} was not found in {sequence}")
Acerca de este algoritmo

Declaración de problema

Dada una matriz de n elementos, escriba una función para buscar el índice de un elemento determinado (destino)

Enfoque

  • Comience a iterar con el primer elemento de la matriz.
  • Compararlo con el elemento objetivo.
  • Si es igual al elemento de destino, devuelva el índice.
  • De lo contrario, continúe iterando.
  • Devolver -1 si el elemento de destino no se encuentra en la matriz.

Complejidad temporal

O(n) Peor caso O(1) Mejor caso (Si el primer elemento de matriz es el elemento de destino)

Complejidad espacial

O(1)

Ejemplo

arr = [1, 3, 9, 5, 0, 2]  

target = 5
La búsqueda lineal debe devolver el índice 3, ya que 5 está en el índice 3.

target = 6           
La búsqueda lineal debe devolver -1 ya que 6 no está presente en la matriz

Enlaces de implementación de código

Explicación en YouTube

Un vídeo CS50 que explica el algoritmo de búsqueda lineal

Explicación de animación