Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 190 vistas

    Búsqueda Secuencial

    Cargado por

    cat
    La búsqueda secuencial involucra recorrer los elementos de una colección de datos de forma lineal o secuencial para encontrar un elemento específico. Requiere comparar el elemento buscado con cada elemento de la colección, tomando una complejidad de O(n) en el caso promedio y peor caso, pero O(1) en el mejor caso si se encuentra al principio. Es un método simple pero lento para conjuntos grandes de datos desordenados.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd

    Búsqueda Secuencial

    Cargado por

    cat
    190 vistas3 páginas
    La búsqueda secuencial involucra recorrer los elementos de una colección de datos de forma lineal o secuencial para encontrar un elemento específico. Requiere comparar el elemento buscado con cada elemento de la colección, tomando una complejidad de O(n) en el caso promedio y peor caso, pero O(1) en el mejor caso si se encuentra al principio. Es un método simple pero lento para conjuntos grandes de datos desordenados.

    Descripción original:

    METODOS DE BUSQUEDAS

    Título original

    Búsqueda secuencial

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    DOCX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    La búsqueda secuencial involucra recorrer los elementos de una colección de datos de forma lineal o secuencial para encontrar un elemento específico. Requiere comparar el elemento buscado con cada elemento de la colección, tomando una complejidad de O(n) en el caso promedio y peor caso, pero O(1) en el mejor caso si se encuentra al principio. Es un método simple pero lento para conjuntos grandes de datos desordenados.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    190 vistas3 páginas

    Búsqueda Secuencial

    Cargado por

    cat
    La búsqueda secuencial involucra recorrer los elementos de una colección de datos de forma lineal o secuencial para encontrar un elemento específico. Requiere comparar el elemento buscado con cada elemento de la colección, tomando una complejidad de O(n) en el caso promedio y peor caso, pero O(1) en el mejor caso si se encuentra al principio. Es un método simple pero lento para conjuntos grandes de datos desordenados.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    Está en la página 1de 3

    Búsqueda secuencial

    Cuando los ítems de datos se almacenan en una colección, por ejemplo en una lista, decimos que tienen
    una relación lineal o secuencial. Cada ítem de datos se almacena en una posición relativa a los demás.
    En las listas, estas posiciones relativas son los valores de los índices de los ítems individuales. Dado que
    estos valores de los índices están ordenados, es posible para nosotros visitarlos en secuencia. Este
    proceso da lugar a nuestra primera técnica de búsqueda, la búsqueda secuencial.

    La Figura 1 muestra cómo funciona esta búsqueda. Comenzando en el primer ítem de la lista,
    simplemente nos trasladamos de un ítem a otro, siguiendo el orden secuencial subyacente hasta que
    encontremos lo que buscamos o nos quedemos sin ítems. Si nos quedamos sin ítems, hemos
    descubierto que el ítem que estábamos buscando no estaba presente.

    Figura 1: Búsqueda secuencial en una lista de enteros

    Análisis de la búsqueda secuencial

    Para analizar los algoritmos de búsqueda, tenemos que tomar una decisión sobre una unidad básica de
    cálculo. Recuerde que éste es típicamente el paso común que debe repetirse para resolver el problema.
    Para buscar, tiene sentido contar el número de comparaciones realizadas. Cada comparación puede o
    no descubrir el ítem que estamos buscando. Además, aquí hacemos otra suposición. La lista de ítems no
    está ordenada de ninguna manera. Los ítems se han colocado al azar en la lista. En otras palabras, la
    probabilidad de que el ítem que estamos buscando esté en una posición determinada es exactamente la
    misma para cada posición de la lista.

    Si el ítem no está en la lista, la única manera de saberlo es compararlo con cada ítem presente. Si hay n
    ítems, entonces la búsqueda secuencial requiere n comparaciones para descubrir que el ítem no está
    allí. En el caso de que el ítem sí esté en la lista, el análisis no es tan sencillo. En realidad hay tres
    escenarios diferentes que pueden ocurrir. En el mejor de los casos encontraremos el ítem en el primer
    lugar que miramos, al principio de la lista. Sólo necesitaremos una comparación. En el peor de los casos,
    no descubriremos el ítem hasta la última comparación, la n-ésima comparación.
    Algoritmo de búsqueda secuencial

    Supongamos que tenemos un array sin clasificar A[] que contiene n elementos, y queremos encontrar
    un elemento - X.

    1.1. Recorre todos los elementos dentro del array comenzando desde el elemento más a la izquierda
    usando un bucle for y haz lo siguiente:
    1.1. Si el valor de A[i] coincide con X, devuelva el índice i. (Si puede haber varios elementos que
    coincidan con X, en lugar de devolver el índice i, imprima todo indexa o almacena todos los índices
    en un array y devuelve ese array).
    1.2. De lo contrario, pase al siguiente elemento.
    1.3. Si está en el último elemento del array, salga del bucle for.
    1.2. Si ninguno de los elementos coincide, devuelve -1.

    Ejemplo de búsqueda secuencial

    Supongamos que tenemos el array: (5, 3, 4, 2, 1, 6).

     Caso 1: Queremos buscar X = 5.

    El primer elemento en sí es una coincidencia y devolvemos el índice 0. (Mejor caso)

     Caso 2: Queremos buscar X = 1.

    Atravesamos el array y llegamos al índice 4 para encontrar una coincidencia y devolver ese índice. (Caso
    promedio)

     Caso 3: Queremos buscar X = 9

    Atravesamos el array pero no encontramos una coincidencia cuando llegamos al último elemento del
    array. Devolvemos -1. (Peor de los casos)

    Complejidad del algoritmo de búsqueda lineal

     Caso promedio

    La complejidad temporal del algoritmo de búsqueda lineal es O(n).

     Mejor caso

    La complejidad del tiempo en el mejor de los casos es O(1). Ocurre cuando el elemento a buscar es el
    primer elemento presente dentro del array.

     Peor caso

    El peor de los casos ocurre cuando el elemento que estamos buscando no está presente dentro del array
    o está en el último índice del array. La complejidad de tiempo en el peor de los casos es O(n).
    Ventajas:

    Es un método sumamente simple que resulta útil cuando se tiene un conjunto de datos pequeños.

    Si los datos buscados no están en orden es el único método que puede emplearse para hacer dichas
    búsquedas.

    Desventajas:

    Este método tiende hacer muy lento.

    Se requiere buscar en todo el arreglo, lo que hace el proceso muy largo.

    Jindal, H. (2021, 11 marzo). Búsqueda lineal. Delft Stack. Recuperado el 13 de diciembre de

    2021, de https://www.delftstack.com/es/tutorial/algorithm/linear-search/

    5.3. La búsqueda secuencial — Solución de problemas con algoritmos y estructuras de datos. (s.

    f.). runestone.academy. Recuperado el 13 de diciembre de 2021, de

    https://runestone.academy/runestone/static/pythoned/SortSearch/LaBusquedaSecuencial.

    html

    403 Forbidden. (s. f.). ed.team. Recuperado el 13 de diciembre de 2021, de

    https://ed.team/comunidad/ventajas-y-desventajas-de-la-busqueda-lineal

    También podría gustarte