Estoy tratando de escribir una función para devolver un subconjunto de una matriz de entrada ordenada donde todos los números están dentro del rango de entrada. Por ejemplo:
getNumsWithin([1,2,3,5,6,7], [3.3, 6.7]) // [5, 6]
getNumsWithin([1,2,3,5,6,7], [6, 7]) // [6, 7]
getNumsWithin([1,2,3,5,6,7], [8, 10]) // []
Dado que la matriz de entrada siempre está ordenada, supongo que puedo usar la búsqueda binaria para encontrar un índice de inicio y un índice final y simplemente dividir la matriz original con ellos.
Aquí está mi intento:
function findStartIdx(sortedArray, target) {
let start = 0,
end = sortedArray.length - 1
while (start < end) {
const mid = Math.floor((start + end) / 2)
if (sortedArray[mid] < target) start = mid
else end = mid - 1
}
return start + 1
}
function findEndIdx(sortedArray, target) {
let start = 0,
end = sortedArray.length - 1
while (start < end) {
const mid = Math.floor((start + end) / 2)
if (sortedArray[mid] < target) start = mid + 1
else end = mid
}
return end + 1
}
function getNumsWithin(array, range) {
const startIndex = findStartIdx(array, range[0])
const endIndex = findEndIdx(array, range[1])
return array.slice(startIndex, endIndex + 1)
}
Pero la búsqueda binaria terminaría siendo un bucle sin fin si el objetivo llega al último número de la matriz. También me pregunto si podemos buscarlo una vez en lugar de dos veces para encontrar tanto el inicio como el final.
Estoy luchando para escribir tal función. ¿Alguien me puede ayudar?
Tu idea está bien, pero las funciones de búsqueda binaria necesitan algunos cambios:
while debe permitir que el start y el end sean iguales.target en la segunda versión debe ser diferente para que se incluyan valores iguales en el rango final.Aquí hay una corrección de ambos:
function findStartIdx(sortedArray, target) {
let start = 0,
end = sortedArray.length - 1
while (start <= end) {
const mid = Math.floor((start + end) / 2)
if (sortedArray[mid] < target) start = mid + 1
else end = mid - 1
}
return start
}
function findEndIdx(sortedArray, target) {
let start = 0,
end = sortedArray.length - 1
while (start <= end) {
const mid = Math.floor((start + end) / 2)
if (sortedArray[mid] <= target) start = mid + 1
else end = mid - 1
}
return end
}
En una nota final: en términos de complejidad de tiempo, estaría bien realizar solo una búsqueda binaria y luego continuar con una búsqueda lineal a través de la matriz. Esto se debe a que tomar el segmento representa la misma complejidad de tiempo que buscar el final del segmento con una búsqueda lineal: ambos son O (tamaño de segmento). Pero dado que en JavaScript el método de slice es rápido en comparación con una búsqueda lineal más "manual" con un bucle explícito, obtendrá mejores resultados con estas dos búsquedas binarias.
Solo necesita asegurarse de que findStartIdx funcione, luego el resto es fácil. Entonces, en lugar de buscar una coincidencia exacta como en la búsqueda binaria normal, buscamos una coincidencia entre dos números en el índice mid y mid + 1 .
Casos extremos: no he probado si los mismos números aparecen varias veces. Necesito arreglar findEndIdx un poco.
var arr = [1, 2, 3, 5, 6, 7]
var start = 0
var end = arr.length - 1;
console.log(getNumsWithin(arr, [3.3, 6.7]))
console.log(getNumsWithin(arr, [6, 7]))
console.log(getNumsWithin(arr, [8, 10]))
function findStartIdx(sortedArray, x, start, end) {
if (start > end) return -1;
let mid = Math.floor((start + end) / 2);
if (arr[mid] <= x) {
if (mid === arr.length - 1) {
return mid;
}
if (arr[mid + 1] >= x) return mid;
return findStartIdx(sortedArray, x, mid + 1, end);
} else {
return findStartIdx(sortedArray, x, start, mid - 1);
}
}
// hehe
function findEndIdx(sortedArray, x, start, end) {
var result = findStartIdx(sortedArray, x, start, end) + 1
if (result == sortedArray.length) return -1;
return result;
}
function getNumsWithin(array, range) {
const startIndex = findStartIdx(array, range[0], start, end)
const endIndex = findEndIdx(array, range[1], start, end)
if (startIndex == -1 || endIndex == -1) {
return [];
}
return array.slice(startIndex, endIndex + 1)
}