javascript - recursiva - busqueda binaria visual basic
Búsqueda binaria en Javascript (20)
Estoy tratando de implementar un algoritmo de búsqueda binario en JavaScript. Las cosas parecen estar bien, pero mis declaraciones de devolución parecen estar volviendo indefinidas? ¿Alguien puede decir lo que está mal aquí?
Fiddle: http://jsfiddle.net/2mBdL/
Gracias.
var a = [
1,
2,
4,
6,
1,
100,
0,
10000,
3
];
a.sort(function (a, b) {
return a - b;
});
console.log(''a,'', a);
function binarySearch(arr, i) {
var mid = Math.floor(arr.length / 2);
console.log(arr[mid], i);
if (arr[mid] === i) {
console.log(''match'', arr[mid], i);
return arr[mid];
} else if (arr[mid] < i && arr.length > 1) {
console.log(''mid lower'', arr[mid], i);
binarySearch(arr.splice(mid, Number.MAX_VALUE), i);
} else if (arr[mid] > i && arr.length > 1) {
console.log(''mid higher'', arr[mid], i);
binarySearch(arr.splice(0, mid), i);
} else {
console.log(''not here'', i);
return -1;
}
}
var result = binarySearch(a, 100);
console.log(result);
Búsqueda binaria ES6
// bottom-up
function binarySearch (arr, val) {
let start = 0;
let end = arr.length - 1;
while (start <= end) {
let mid = Math.floor((start + end) / 2);
if (arr[mid] === val) {
return mid;
}
if (val < arr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
enfoque diferente:
// recursive
function binarySearch(arr, val, start = 0, end = arr.length - 1) {
const mid = Math.floor((start + end) / 2);
if (val === arr[mid]) {
return mid;
}
if (start >= end) {
return -1;
}
return val < arr[mid]
? binarySearch(arr, val, start, mid - 1)
: binarySearch(arr, val, mid + 1, end);
}
¡Esta es mi solución!
// perform a binarysearch to find the position in the array
function binarySearch(searchElement, searchArray) {
''use strict'';
var stop = searchArray.length;
var last, p = 0,
delta = 0;
do {
last = p;
if (searchArray[p] > searchElement) {
stop = p + 1;
p -= delta;
} else if (searchArray[p] === searchElement) {
// FOUND A MATCH!
return p;
}
delta = Math.floor((stop - p) / 2);
p += delta; //if delta = 0, p is not modified and loop exits
}while (last !== p);
return -1; //nothing found
};
Acabo de encontrar esta implementación de splice en la revisión de código, así que creo que es importante aclarar qué tan mala es esta implementación.
En primer lugar, BinarySearch es un algoritmo que en O (log (n)) en la matriz ordenada encuentra un índice en el que podemos insertar nuestro elemento y aún tener la matriz ordenada (podemos usarlo también para encontrar el elemento más cercano, así que para responder algunas preguntas en los comentarios) - Hay un sentido de devolver un valor. Puede ser un valor diferente del que está consultando.
En la implementación de splice hay un fallo de diseño importante: el algoritmo de búsqueda modifica la matriz consultada. Imagine que tiene una base de datos y consulta SELECT * FROM data WHERE id=1 y se elimina la mitad de su tabla. La clonación de la matriz antes de pasar a BinarySearch no es muy útil, pero explicaré por qué en el siguiente párrafo.
Así que corrigamos este fallo de diseño y usamos una nueva slice función que funcionaría igual que el splice pero no modificaría la matriz (solo devolvería los elementos seleccionados). Todavía hay una gran falla en el algoritmo. Para n=2^m array hacemos m pruebas. Después de lo primero, regresaríamos de los elementos de la slice n/2 , la próxima vez que sea n/4 , luego n/8 etc. Si resumimos esto serán n-1 elementos. Así que tenemos el algoritmo O(n) y es tan rápido como la búsqueda lineal, pero mucho más complicado (la búsqueda lineal es incluso más rápida, porque su costo promedio es n/2 y el slice BinarySearch siempre es n-1 ). La implementación del splice original es aún peor: cada splice necesitaría además mover elementos en la tabla, por lo que, en el peor de los casos, sería n segundo n/2 tercero n/4 por lo que al final sería 2 * n - 1 - y esta es la razón por la que la matriz de clonación no es muy útil (la clonación es O(n) así que nunca clone su matriz antes de pasar a un buen algoritmo de búsqueda binaria)
Aquí está la función de búsqueda binaria, puede comprobar
function bsearch (Arr,value){
var low = 0 , high = Arr.length -1 ,mid ;
while (low <= high){
mid = Math.floor((low+high)/2);
if(Arr[mid]==value) return mid ;
else if (Arr[mid]<value) low = mid+1;
else high = mid-1;
}
return -1 ;
}
Aquí hay una función ES6 en estilo de programación funcional , que usa una función de comparación predeterminada si no se proporciona: si el valor buscado es del tipo numérico, se asumirá la comparación numérica, de lo contrario, la comparación de cadenas.
function binarySearch(arr, val, compFunc =
(a, b) => typeof val == ''number'' ? a-b : a.localeCompare(b), i=0, j=arr.length) {
return i >= j ? i
: ( mid =>
( cmp =>
cmp < 0 ? binarySearch(arr, val, compFunc, i, mid)
: cmp > 0 ? binarySearch(arr, val, compFunc, mid+1, j)
: mid
) (compFunc(val, arr[mid]))
) (i + j >> 1);
}
///////// Tests ///////////////////
function check(arr, val, compFunc) {
var fmt = JSON.stringify;
var result = binarySearch(arr, val); // default compFunc is assumed
console.log(`binarySearch(${fmt(arr)}, ${fmt(val)}) == ${fmt(result)}`);
if (result > arr.length || result < 0 || !arr.length && result
|| result < arr.length && compFunc(val, arr[result]) > 0
|| result > 0 && compFunc(val, arr[result-1]) < 0) throw "Unexpected result!!!"
}
// Tests with numeric data:
for (var val = 0; val < 12; val++)
check([1, 2, 4, 6, 9, 9, 10], val, (a,b) => a-b);
// Test with empty array:
check([], 12, (a,b) => a-b);
// Test with string data:
check([''abc'', ''deaf'', ''def'', ''g''], ''dead'', (a, b) => a.localeCompare(b));
Buenas tardes, entiendo que esta publicación comenzó hace algún tiempo, sin embargo, pensé que posiblemente podría contribuir a la discusión.
function binarySearch(array, target, max, min) {
//Find the Midpoint between forced max and minimum domain of the array
var mid = ((max - min) >> 1) + min;
//alert("Midpoint Number" + mid);
console.log(mid);
console.log(array[mid], "target: " + target);
if (array[mid] === target) {
//Target Value found
console.log(''match'', array[mid], target);
//alert(''match'', array[mid], target);
return mid;
}
else if (mid === 0)
{
//All Value have been checked, and none are the target value, return sentinel value
return -1;
}
else if (array[mid] > target)
{
//Value at Midpoint is greater than target Value, set new maximum to current midpoint
max = mid;
console.log(''mid lower'', array[mid], target);
//alert(''mid lower'', array[mid], target);
//Call binarySearch with new search domain
return binarySearch(array, target, max, min);
}
else if (array[mid] < target)
{
// Value at Midpoint is less than the target Value, set new minimum to current midpoint
min = mid;
console.log(''mid higher'', array[mid], target);
//alert(''mid higher'', array[mid], target);
//Call binarySearch with new search domain
return binarySearch(array, target, max, min);
}
Estoy seguro de que hay espacio para refinamiento aquí, pero este método evita tener que realizar una copia profunda de la matriz (lo que puede ser una acción costosa cuando se trabaja con un gran conjunto de datos) y, al mismo tiempo, no modifica la matriz de cualquier manera.
¡Espero que ayude! Gracias jeremy
Es útil escribir una función de búsqueda de tal manera que devuelva un valor negativo que indique el punto de inserción para el nuevo elemento si no se encuentra el elemento. Además, el uso de la recursión en una búsqueda binaria es excesivo e innecesario. Y, finalmente, es una buena práctica hacer que el algoritmo de búsqueda sea genérico al proporcionar una función de comparación como parámetro. A continuación se muestra la implementación.
function binarySearch(ar, el, compare_fn) {
var m = 0;
var n = ar.length - 1;
while (m <= n) {
var k = (n + m) >> 1;
var cmp = compare_fn(el, ar[k]);
if (cmp > 0) {
m = k + 1;
} else if(cmp < 0) {
n = k - 1;
} else {
return k;
}
}
return -m - 1;
}
Este código con comentarios y una prueba de unidad here .
Hay muchas soluciones viables para esta pregunta, pero todas regresan temprano una vez que han encontrado una coincidencia. Si bien esto podría tener un pequeño efecto positivo en el rendimiento, esto es despreciable debido a la naturaleza logarítmica de la búsqueda binaria y puede dañar el rendimiento si la función de comparación es costosa de calcular.
Además, evita una aplicación muy útil del algoritmo de búsqueda binaria: encontrar un rango de elementos coincidentes, también conocido como encontrar el límite inferior o superior .
La siguiente implementación devuelve un índice 0 ≤ i ≤ array.length tal que el predicado dado es false para la array[i - 1] y true para la array[i] . Si el predicado es false todas partes, se devuelve array.length .
/**
* Return 0 <= i <= array.length such that !pred(array[i - 1]) && pred(array[i]).
*/
function binarySearch(array, pred) {
let lo = -1, hi = array.length;
while (1 + lo < hi) {
const mi = lo + ((hi - lo) >> 1);
if (pred(array[mi])) {
hi = mi;
} else {
lo = mi;
}
}
return hi;
}
Supongamos por el bien del argumento que pred(array[-1]) === false y pred(array[array.length]) === true (aunque, por supuesto, el predicado nunca se evalúa en esos puntos). El bucle mantiene el invariant !pred(array[lo]) && pred(array[hi]) . El algoritmo finaliza cuando 1 + lo === hi que implica !pred(array[hi - 1]) && pred(array[hi]) , la condición posterior deseada.
Si una matriz se sort() con respecto a una comparación de la función de compare , la función devuelve la posición de inserción más pequeña de un item cuando se invoca como
binarySearch(array, j => 0 <= compare(item, j));
Una posición de inserción es un índice en el que se encontraría un elemento si existiera en la matriz.
Es fácil implementar el límite inferior y superior para una matriz en orden natural de la siguiente manera.
/**
* Return i such that array[i - 1] < item <= array[i].
*/
function lowerBound(array, item) {
return binarySearch(array, j => item <= j);
}
/**
* Return i such that array[i - 1] <= item < array[i].
*/
function upperBound(array, item) {
return binarySearch(array, j => item < j);
}
Por supuesto, esto es más útil cuando la matriz puede contener varios elementos que se comparan de manera idéntica, por ejemplo, cuando los elementos contienen datos adicionales que no forman parte de los criterios de clasificación.
Joki tuvo la idea correcta, sin embargo, su versión no funcionó para matrices vacías: devolvió 0 lugar de -1 . Y, hay dos optimizaciones adicionales que podrían agregarse a su versión. Por lo tanto, aquí está mi versión mejorada.
function binarySearch(array, pred) {
let lo = -1, hi = array.length;
binsearch: while (1 + lo !== hi) {
const mi = (hi + lo) >> 1;
if (pred <= array[mi]) {
hi = mi;
continue binsearch;
}
lo = mi;
}
return array[hi] === pred ? hi : -1;
}
Manifestación:
let textarea = document.getElementById(''inputbox''),
searchinput = document.getElementById(''search''),
resultbox = document.getElementById(''result''),
timeoutID;
textarea.oninput = searchinput.oninput = function(e){
clearTimeout( timeoutID );
timeoutID = setTimeout(requestAnimationFrame.bind(window,function(){
try {
var txt = textarea.value
.replace(//s*/[|/]/s*/g, '''')
.split('',''),
arr = JSON.parse(textarea.value),
searchval = eval(searchinput.value),
textmtchs = textarea.value
.match(//s*/[|/]/s*/g);
txt = refSort(txt, arr);
textarea.value = textmtchs[0] +
txt.join('','') +
textmtchs[textmtchs.length-1];
arr = JSON.parse(textarea.value);
resultbox.value = binarySearch(arr, searchval);
} catch(e) {
resultbox.value = ''Error'';
}
}), +((e.target === textarea) && 1111));
}
function refSort(targetData, refData) {
var indices = Object.keys(refData);
indices.sort(function(indexA, indexB) {
if (refData[indexA] < refData[indexB]) return -1;
if (refData[indexA] > refData[indexB]) return 1;
return 0;
});
return indices.map(function(i){ return targetData[i] })
}
function binarySearch(array, pred) {
let lo = -1, hi = array.length;
binsearch: while (1 + lo !== hi) {
const mi = (hi + lo) >> 1;
if (pred <= array[mi]) {
hi = mi;
continue binsearch;
}
lo = mi;
}
return (array[hi] == pred) ? hi : -1;
}
<h3 style="margin:.125em;width:100%;text-align:center">The Array (Must Be A Valid JSON Array)</h3>
<textarea placeholder="[-24, -12, 0, 0, 9, 16, 18, 64, 80]" type="text" rows=6 style="width:calc(100% - .5em);display:block" id="inputbox">[-24, -12, 0, 0, 9, 16, 18, 64, 80]</textarea>
<div style="white-space:pre-wrap;tab-size:8">
<h3 style="margin:.125em;display:inline">Search Value: </h3><input type="text" id="search" value="-12" style="width:8em;text-align:center" />
<h3 style="margin:.125em;display:inline">Resulting Index: </h3><input type="text" id="result" value="1" style="width:8em;text-align:center" readonly />
</div>
También puede usar una serie de cadenas (entre comillas) en la demostración, y debería funcionar bien.
No está devolviendo explícitamente las llamadas internas recursivas (es decir, return binarySearch() ), por lo que la pila de llamadas se despliega sin valor de retorno. Actualice su código de esta manera:
// ...
if (arr[mid] === i) {
console.log(''match'', arr[mid], i);
return arr[mid];
} else if (arr[mid] < i && arr.length > 1) {
console.log(''mid lower'', arr[mid], i);
return binarySearch(arr.splice(mid, Number.MAX_VALUE), i);
} else if (arr[mid] > i && arr.length > 1) {
console.log(''mid higher'', arr[mid], i);
return binarySearch(arr.splice(0, mid), i);
} else {
// ...
Ver un violín de trabajo
No puedes usar la búsqueda binaria para una matriz sin clasificar. debería tener [1, 4, 13, 77 ...] pero no [1, 2, 13, 5, 17 ...] ... mi mal, lo hizo sortear ()
Quiero agregar mi función de búsqueda binaria searchArray , junto con las funciones de la utilidad de herramienta insertSortedArray y removeSortedArray a la lista de respuestas, ya que creo que está limpio, es de uso global y creo que es bastante rápido.
Supongamos que la matriz está ordenada (escriba su propio algoritmo ordenado o simplemente use métodos incorporados)
function bSearch(array,item){
var start = 0,
end = item.length - 1;
var middle = Math.floor((end+start)/2);
while(array[middle] !== item && start < end){
if(item < array[middle]){
end = middle-1;
}
else if(item > array[middle]){
start = middle+1;
}
middle = Math.floor((end+start)/2);
}
if(array[item]!== middle){
console.log(''notFoundMate);
return -1;
}
else {
console.log(''FoundMate);
return middle;
}
}
Suponiendo una matriz ordenada, aquí hay una búsqueda binaria recursiva:
function binSearch(needle, arr) {
length = arr.length;
while(length > 1) {
midpoint = Math.floor(length/2);
return (needle > arr[midpoint-1]) ?
binSearch(needle, arr.splice(midpoint, length)) :
binSearch(needle, arr.splice(0, midpoint));
}
return needle === arr[0] ? arr[0] : -1;
}
También debe verificar el caso del borde "valor no encontrado" y convertirlo en su primera condición de base, seguido de una búsqueda exitosa. Por lo tanto, no es necesario verificar la longitud de la matriz> 1 cuando se realiza la repetición a través de la matriz. Finalmente, ya que no devuelve la matriz, ¿por qué no usa el método Array.prototype.slice?
var binarySearch = function(arr, val) {
var half = Math.floor(arr.length / 2);
if (arr.length === 0) {
return -1;
}
else if (arr[half] === val) {
console.log("val: ", val, "arr[half]: ", arr[half]);
return val;
}
else if (val > arr[half]) {
console.log("val: ", val, "arr[half]: ", arr[half]);
return binarySearch(arr.slice(half, arr.length), val);
}
else {
console.log("val: ", val, "arr[half]: ", arr[half]);
return binarySearch(arr.slice(0, half), val);
}
}
var arr = [1, 5, 20, 58, 76, 8, 19, 41].sort(function(a, b) { return a - b });
console.log("Sorted array: " + arr);
console.log(binarySearch(arr, 76));
console.log(binarySearch(arr, 19));
console.log(binarySearch(arr, 0));
Tengo una implementación en github con una comparación entre binario y lineal y una página de prueba si aún está interesado en ver más implementaciones here
para usarlo, simplemente copie y péguelo tal cual, para usar las variables locales para la velocidad. y modifique el valor buscado como si busca en subobjetos o matrices:
if (array[mid][0] < value[0]) low = mid + 1;
if (array[mid].val < value.val) low = mid + 1;
para obtener resultados más rápidos, utilice matrices o matrices de matrices o matrices paralelas, copie las matrices buscadas en las variables locales. variables no locales o cada vez que haces obj.something se ralentiza.
Esta es la versión más rápida es así:
let array=[3,4,5,6]
let value=5; //searched value
let mid, low = 0,high = array.length;
while (low < high) {
mid = low + high >>> 1; // fast divide by 2 and round down
if (array[mid] < value) low = mid + 1;
else high = mid;
}
//if (array[mid] != value) mid=-1;// this might not be required if you look for place to insert new value
mid;// contains the found value position or if not found one before where it would be if it was found
La búsqueda binaria funciona así:
| . | // find middle
//option 1:
| . v | // if value on right, middle is top
| . | // so then it is like this
//option 2:
| v . | // if value on left, middle is bottom
| . | // so then it is like this
//more loops of option 2 until not found
| . | // next time it will be like this
|. | // next time it will be like this
. // next time it will be like this
esta implementación va a la parte inferior si no se encuentra. Se puede encontrar o no siempre. devuelve el índice a continuación o es igual al valor buscado. por lo que hay que comprobar si es igual. para validar si el valor existe o es solo un resultado a continuación. Si está buscando un lugar para insertar una orden de posada, solo coloque en ese lugar, no es necesario verificar si es igual a
function binarySearch(arr, num, l, r){
if( arr instanceof Array ){
l = isNaN(l) ? 0 : l;
r = isNaN(r) ? arr.length - 1: r;
let mid = l + 1 + Math.round((r - l)/2 - 1);
console.log(l, r, mid, arr[mid]);
if( num == arr[mid] ){
console.log("found");
return mid;
}
if( typeof arr[mid] == "undefined" || l == r ){
console.log("not found"); return -1;
}
if( num < arr[mid] ){
console.log("take left");
return binarySearch(arr, num, l, r - mid);
}
console.log("take right");
return binarySearch(arr, num, mid, r);
}
}
console.log( binarySearch([0, 0, 1 ,1, 2, 3, 5, 6, 11], 2) );
function binarySearch(a = [], x) {
let length = a.length;
if (length === 0) {
return false;
} else {
let m = Math.floor(length/2);
let y = a[m];
if (x === y) {
return true;
} else if (x < y) {
return binarySearch(a.slice(0, m), x);
} else {
return binarySearch(a.slice(m + 1), x);
}
}
}