Tengo una matriz de objetos que sé que está ordenada por una de las propiedades del objeto. Quiero buscar en la matriz el objeto con esa propiedad igual a un valor específico, así que hago esto:
arrOfObjects.find((obj) => obj.property === value) Sin embargo, esta es una operación O(n) para una matriz no ordenada, pero O(log n) usando búsqueda binaria en matrices ordenadas.
¿Hay alguna forma de decirle a JavaScript que mi matriz está ordenada al hacer un .find() , o tengo que implementar manualmente una búsqueda binaria?
No hay una funcionalidad de búsqueda binaria incorporada en JavaScript.
Incluso si hubiera Array#find() en sí mismo no puede beneficiarse de él, ya que espera una devolución de llamada que devuelve true o false . No hay forma de determinar si el resultado esperado está antes o después de un punto determinado en función de un resultado booleano que solo indica una coincidencia.
Podría implementar un prototipo de Array , como
Array.prototype.binaryFind = function (callbackFn, thisArg) { // code };Luego, debe especificar una función como devolución de llamada que tenga tres estados para determinar el lado izquierdo o derecho de búsqueda. Una idea es tomar el mismo enfoque que para ordenar donde un valor toma el orden, dependiendo de negativo, cero o positivo, lo que muestra la relación de los valores.
function findInObjects(key, value) { return function (object, index, array) { // if (object[key] === value) return 0; if (object[key] < value) return -1; else return 1; } }