Imaginemos un mundo libre – El blog de Ronny

La paz interior comienza en el momento en el que decides no permitir, que ninguna persona o evento, tome el control de tus emociones.

Búsqueda lineal y búsqueda binaria

with 7 comments

Los algoritmos de búsqueda lineal y binaria son 2 de los algoritmos más usados para encontrar elementos en una estructura de datos.

La búsqueda lineal probablemente es sencilla de implementar e intuitiva. Básicamente consiste en buscar de manera secuencial un elemento, es decir, preguntar si el elemento buscado es igual al primero, segundo, tercero y así sucesivamente hasta encontrar el deseado.

Entonces este algoritmo tiene una complejidad de O(n).

La búsqueda binaria al igual que otros algoritmos como el quicksort utiliza la técnica divide y vencerás. Uno de los requisitos antes de ejecutar la búsqueda binaria, es que el conjunto de elementos debe de estar ordenado. Supongamos que tenemos el siguiente array.

57 53 21 37 17 36 22 3 44 97 89 26 31 47 8 17

Debemos ordenarlo
3 8 17 17 21 22 26 31 36 37 44 47 53 57 89 97

¿Como funciona la búsqueda binaria? 
Necesitamos una seria de datos para realizar la búsqueda: El elemento en la posición inicio, fin, medio. Y porsupuesto el tamaño del vector y elemento que queremos buscar.

    int first = 0;
    int middle = 0;
    int last = arraySize - 1;
    middle = (first + last) / 2;

Preguntamos si el elemento buscado es igual al elemento que se encuentra en la posicion medio del array, si es afirmativo ya encontramos el elemento y no hay nada más que hacer.

        if (searched == array[middle]) {
            cout << "Se encuentra en la posición " << middle + 1 << endl;
            return array[middle];
        }

Si no es así. Preguntamos si el elemento que se encuentra en la posición medio es mayor al elemento buscado, si es afirmativo y como el array está ordenado, quiere decir que elemento buscado es menor al del medio. Entonces ahora solo buscaríamos en esa división del array,
por lo tanto, el fin ahora sería el elemento anterior al medio.

            if (array[middle] > searched) {
                last = middle - 1;
            }

De lo contrario quiere decir que elemento buscado es mayor al del medio, entonces debemos buscar en la otra división del array, por lo tanto el inicio sería el elemento posterior al medio.

            else {
                first = middle + 1;
            }

Con cualquiera de estas 2 operaciones descartamos la otra mitad del array y por lo tanto reducimos notablemente el número de iteraciones.

Por lo tanto, en cada iteración, la búsqueda se reduce a la mitad del array. Realizamos esto en un bucle mientras el inicio sea menor o igual al fin.

El algoritmo de búsqueda binaria tiene una complejidad de O(log n).

Veamos la implementación de la búsqueda lineal y binaria en C++.

Aquí tienen el código del algoritmo y una breve explicación.

#include <iostream>
#include <stdlib.h>
#include "quicksort.cpp"

using namespace std;

int lineal_search(int *array, int searched, int arraySize)
{
    for (int i = 0; i< arraySize; i++) {
        if (searched == array[i]) {
            cout << "Se encuentra en la posicion " << i + 1 << endl;
        }
   }
}

int binary_search(int *array, int searched, int arraySize)
{
    int first = 0;
    int middle;
    int last = arraySize - 1;

    while (first <= last) {
        middle = (first + last) / 2;

        if (searched == array[middle]) {
            cout << "Se encuentra en la posición " << middle + 1 << endl;
            return array[middle];
        } else {
            if (array[middle] > searched) {
                last = middle - 1;
            } else {
                first = middle + 1;
            }
        }
    }
    return -1;
}

void print(int *array, int arraySize)
{
   for (int i = 0; i < arraySize; i++) {
        cout << array[i] << "  ";
   }
   cout << endl << endl;
}

int main()
{
    int arraySize;
    int searched;
    cout << "Ingresa el tamanyo del array" << endl;
    cin >> arraySize;

    int array[arraySize];

    srand(time(NULL));
    for (int i = 0; i < arraySize; i++) {
        array[i] = rand() % 100;
    }

    cout << endl;
    cout << "Array al inicio: " << endl;
    print(array, arraySize);

    cout << "Busqueda lineal -> Ingresa el elemento a buscar: ";
    cin >> searched;
    lineal_search(array, searched, arraySize);

    cout << "Array ordenado: " << endl;
    quicksort(array, 0, arraySize);
    print(array, arraySize);

    cout << "Busqueda binaria -> Ingresa el elemento a buscar: ";
    cin >> searched;
    binary_search(array, searched, arraySize);
}

Ejemplo de la salida del programa:

Ingresa el tamanyo del array
16

Array al inicio
57  53  21  37  17  36  22  3  44  97  89  26  31  47  8  17

Ingresa el elemento a buscar (Busqueda lineal) 36
El elemento se encuentra en la posicion 6
Array ordenado
3  8  17  17  21  22  26  31  36  37  44  47  53  57  89  97

Ingresa el elemento a buscar (Busqueda binaria) 89
El elemento se encuentra en la posicion 15

Nota: Para realizar la búsqueda binaria, estoy incluyendo el archivo que contiene el algoritmo de ordenamiento quicksort, para no volver a escribirlo y así reutilizar código.

El quicksort.cpp lo pueden encontrar aquí: http://ronnyml.wordpress.com/2009/07/19/quicksort-en-c/

El código fuente de este y otros ejercicios de C++ está disponible en Github:

https://github.com/ronnyml/C—Tutorial

Gracias por tu visita al blog. Puedes seguirme en Twitter haciendo click en el siguiente enlace:

About these ads

Written by Ronny Yabar Aizcorbe

julio 9, 2009 at 6:31 pm

7 comentarios

Subscribe to comments with RSS.

  1. La verdad es que estuve teniendo complicaciones con algunas formas de trabajar con vectores, este articulo que publicaste me di{o una idea para mejorar algunos algoritmos que estaba realizando.

    marck

    noviembre 28, 2009 at 9:55 pm

  2. excelente ejemplo, gracias!

    Guido

    mayo 11, 2010 at 11:32 pm

  3. me ayudastes mucho a entender lo que son los vectores y sus arreglos “GRACIAS2

    ALEXAR

    septiembre 20, 2011 at 5:24 pm

  4. buenisimo

    valeria

    noviembre 7, 2011 at 12:28 am

  5. gracias por el ejmplo……. aunque yo lo que buscaba era una lista de ejemplos para una tarea………… pero muchas gracias……..

    isaias chavez

    mayo 22, 2012 at 8:48 am

  6. Gracias por publicar esto,me sirvió la lógica del programa y logre hacerlo correr en Visual Basic. Saludos

    Marcos Gomzalez

    julio 29, 2014 at 12:53 pm


Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

A %d blogueros les gusta esto: