Aventuras de DoHITB: Buscar como el rayo

Buenas!

¿Tiempo sin escribir? apenas... jeje

Bueno, como supondréis mis ávidos lectores, ¡voy de culo! Mi vida últimamente es un caos... operaciones, muchos proyectos y mucho trabajo.

Sí, ya llevo casi dos años en mi nuevo trabajo y estoy muy contento. También he estado volcado casi en cuerpo y alma a hacer Cosplay (los que me sigáis por YouTube ya lo habréis visto ;-) )

Bueno, ya que con el poco tiempo que tengo es difícil adelantar los proyectos he decidido redactar una micro-aventura que me sucedió mientras planeaba una entrada sorpresa para vosotros.

¿Preparados?

¡Vamos allá!

Pues estaba yo en pensando en ofrecer algo con valor añadido... y se me ocurrió un método de búsqueda bastante eficiente. La única condición para usarlo es que está basado en un Array ordenado, pero para eso tenemos nuestro objeto JavaScript, ¿no? :D

Bien, el algoritmo de esta búsqueda se basa en una función recursiva, de manera que hacemos lo siguiente:

Tomamos el array, y calculamos su longitud (y la guardamos). Dividimos la longitud en dos para tomar el elemento del medio, y lo comparamos con el elemento que queremos buscar.

Si el elemento es mayor, tomamos la mitad superior del array, y la longitud pasa a ser el punto medio.

Con este nuevo array y esta nueva longitud volvemos al primer paso, y vamos iterando hasta que tengamos un array de 2 posiciones; en este punto con un simple condicional podemos discriminar el valor.

¿Qué ganamos con esto? Sencillo: mucha velocidad.

Es decir, imaginemos un array de 1.000 posiciones, y queremos buscar el elemento que está en la posición 900.

En una búsqueda lineal (la típica) haríamos 900 pasos a través de un "for" con sus 900 "if's".

En una búsqueda como la propuesta, el número de pasos se reduce a menos de 15 pasos, la diferencia de rendimiento es brutal.

Ahora pensaréis que claro, primero se tiene que ordenar el Array, pero yo os pregunto: ¿acaso no es cierto que el 90% de datos de un Array están entrados a mano o vienen de una base de datos?

En ambos casos se puede ordenar, ¿no? pues eso :D

Así que me puse manos a la obra y desarrollé un script.

La cosa es que no acaba aquí... me sentía orgulloso de mi descubrimiento, y lo comenté con un compañero de trabajo y me dijo que eso YA EXISTE. Me quedé de piedra... la verdad es que no estoy muy puesto (de momento) en temas de búsqueda, así que busqué y de hecho existe, se llama búsqueda binaria.

Lejos de decepcionarme, me alegró pensar que "llegué a la misma conclusión que las grandes mentes yo solo". No es que me quiera echar flores, pero es así. Se me ocurrió a mí solo, quizá tardé mucho tiempo, pero lo hice; y eso me hace pensar que quizá mis ideas no son siempre descabelladas, y eso me alegra.

En todo caso, es un buen ejemplo de conocimiento autodidacta y de algo eficiente.

Espero que os haya gustado la entrada, que podáis usar sin problemas este script y que os vaya muy bien.

¡Hasta la próxima!

[code lan=gral] function search(gs, ls){ if(gs == 1){ if(gx[0] == ls){ sr = 0; } }else if(gs == 2){ if(gx[0 + offset] == ls){ sr = offset; }else if(gx[1 + offset] == ls){ sr = ++offset; } }else{ if(gs%2 == 1){ sh = ((gs - 1) / 2); }else{ sh = (gs / 2); } if(gx[sh + offset] <= ls){ offset += sh; } if(sh%2 == 0){ search(sh, ls); }else{ search(sh + 1, ls); } } return sr; } [/code]