Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 24 vistas

    Busqueda Dicotómica

    Cargado por

    Santi Auat
    La búsqueda dicotómica es un método de búsqueda en un arreglo ordenado. Se calcula la posición media del arreglo y se compara el elemento en esa posición con el número a buscar. Si no coincide, se descarta la mitad del arreglo y se repite el proceso recursivamente hasta encontrar el número o determinar que no está presente.

    Copyright:

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

    Busqueda Dicotómica

    Cargado por

    Santi Auat
    24 vistas13 páginas
    La búsqueda dicotómica es un método de búsqueda en un arreglo ordenado. Se calcula la posición media del arreglo y se compara el elemento en esa posición con el número a buscar. Si no coincide, se descarta la mitad del arreglo y se repite el proceso recursivamente hasta encontrar el número o determinar que no está presente.

    Descripción original:

    Título original

    Busqueda dicotómica

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

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

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    La búsqueda dicotómica es un método de búsqueda en un arreglo ordenado. Se calcula la posición media del arreglo y se compara el elemento en esa posición con el número a buscar. Si no coincide, se descarta la mitad del arreglo y se repite el proceso recursivamente hasta encontrar el número o determinar que no está presente.

    Copyright:

    © All Rights Reserved
    Descargue como PPSX, PDF, TXT o lea en línea desde Scribd
    Descargar como ppsx, pdf o txt
    24 vistas13 páginas

    Busqueda Dicotómica

    Cargado por

    Santi Auat
    La búsqueda dicotómica es un método de búsqueda en un arreglo ordenado. Se calcula la posición media del arreglo y se compara el elemento en esa posición con el número a buscar. Si no coincide, se descarta la mitad del arreglo y se repite el proceso recursivamente hasta encontrar el número o determinar que no está presente.

    Copyright:

    © All Rights Reserved
    Descargue como PPSX, PDF, TXT o lea en línea desde Scribd
    Descargar como ppsx, pdf o txt
    de 13

    Búsqueda dicotómica

    A
    1 Para poder realizar
    una búsqueda dicotómica,
    2 es necesario
    3 que el arreglo
    esté
    5 ordenado
    8
    Búsqueda dicotómica
    A Luego determino que
    1 elemento quiero encontrar
    2 dentro del arreglo

    3 Leer (num)
    5
    Ejemplo: num = 2
    8
    Búsqueda dicotómica
    A
    1 Para comenzar la búsqueda,
    2 el primer paso
    3 es encontrar
    5 la posición media,
    cómo?
    8
    Búsqueda dicotómica
    A Existen 2 posibilidades para calcular
    la media:
    1
    2 Una opción es

    3 Longitud DIV 2
    5 div 2 = (2,5) = 2
    5
    8
    Búsqueda dicotómica
    A Longitud DIV 2
    5 div 2 = (2,5) = 2
    1
    2 La segunda forma
    para calcular la media es
    3
    5 (Inicio + Fin ) DIV 2
    8 (1 + 5) div 2 = 3
    Búsqueda dicotómica
    A Med = (Inicio + Fin ) DIV 2

    1
    A[med] = num?
    2
    3 3 = 2?
    5 Como no coincide,
    8 Dónde sigo buscando?
    Búsqueda dicotómica
    A Busco en la mitad superior por ser menor,
    descarto todos los mayores, incluido el dato
    1 que estaba en la posición media.

    2 Med = (Inicio + Fin ) DIV 2


    3
    5 A[med] = num?
    8
    Busqueda dicotómica
    A Busco en la mitad superior
    Inicio sigue = 1
    1 Pero ……
    2 Fin = med – 1 (porque en med no estaba)
    Calculo nuevamente el medio
    3
    Med = (Inicio + Fin ) DIV 2
    5
    8 A[med] = num?
    Búsqueda dicotómica
    A Busco en la mitad superior
    Inicio sigue = 1
    1 Pero ……
    2 Fin = med – 1 (porque en med no estaba)

    3 Med = (Inicio + Fin ) DIV 2


    5
    8 A[med] = num?
    Búsqueda dicotómica
    A Como lo que busco es mayor, ahora debo
    hacerlo en la mitad inferior, y descarto el
    1 menor.
    Inicio = med +1 (porque en med no estaba)
    2 y
    3 Fin = 2
    5 Med = (Inicio + Fin ) DIV 2

    8 A[med] = num?
    Búsqueda dicotómica
    En la actual posición media lo encontró
    A A[med] = num
    1
    2 Pero si el dato a buscar
    3 no existía en este arreglo,
    5 con este mecanismo
    8 caería en loop.
    Por lo cual hay que deteminar
    si se encontró el dato que se buscaba,
    poniendo por ejemplo una bandera en estado verdadero

    Además verificar que el límite inferior


    (o sea el inicio)
    no sea mayor que el límite superior
    (o sea el fin),
    esta situación informa que el dato no se encuentra.

    También podría gustarte