forma más rápida de determinar si un elemento está en una matriz ordenada

Question

Tengo una matriz de entradas ordenadas con 1,000 o más valores (podría ser de hasta 5000+). Necesito escribir una función que recibe un int y devuelve un bool basado en el elemento que está en la matriz. Sé que puedo escribir un bucle for con un descanso, sé que puedo usar jquery .InArray.

Cuál sería la mejor manera de implementar esto, SABIENDO que la matriz está ordenada.

Gracias.

Answer 1

Sabiendo que la matriz está ordenada, una búsqueda binaria sería el mejor enfoque.

Answer 2

Si la matriz está ordenada, entonces la respuesta está ordenada: use una chuleta binaria.

Answer 3

Creo que le gustaría usar una rutina de búsqueda binaria. Una rutina de búsqueda binaria es mientras que una búsqueda lineal es, en promedio, .

Hay muchas variaciones para elegir la forma. Aquí hay uno que encontré en this article:

function binarySearch(items, value){ 

    var startIndex = 0, 
     stopIndex = items.length - 1, 
     middle  = Math.floor((stopIndex + startIndex)/2); 

    while(items[middle] != value && startIndex < stopIndex){ 

     //adjust search area 
     if (value < items[middle]){ 
      stopIndex = middle - 1; 
     } else if (value > items[middle]){ 
      startIndex = middle + 1; 
     } 

     //recalculate middle 
     middle = Math.floor((stopIndex + startIndex)/2); 
    } 

    //make sure it's the right value 
    return (items[middle] != value) ? -1 : middle; 
} 

O esta versión más simple mirando desde this article que tiene una función de búsqueda binaria en un trillón de diferentes idiomas.

function binary_search_iterative(a, value) { 
    var lo = 0, hi = a.length - 1, mid; 
    while (lo <= hi) { 
     mid = Math.floor((lo+hi)/2); 
     if (a[mid] > value) 
      hi = mid - 1; 
     else if (a[mid] < value) 
      lo = mid + 1; 
     else 
      return mid; 
    } 
    return null; 
} 

También hay una búsqueda binaria en el cierre de Google con el código here.

Y, una buena descripción de cómo funciona el algoritmo de búsqueda binaria en Wikipedia.

Answer 4

Muchos lenguajes ya tienen esto implementado, por ejemplo, en Java, puedes simplemente usar el método CollectionsCollections.binarySearch (List> list, T key) y estoy seguro de que C# también tiene algún tipo de método BinarySearch.

Answer 5

Si realiza búsquedas más de una vez, migre a un objeto similar a un mapa.

var fastLookup = {}; 
 
mySortedArray.forEach(function(i){fastLookup[i]=true)}); 
 

 
//Each time: 
 
    if (fastLookup[key]===true){ //do thing 
 
    }