1

He intentado hacer lo siguiente pero no entiendo.

El valor esperado debe ser estrictamente igual a 1 y recibo -1.

Este es mi código:

var binarySearch = function (array, i) {
{
    var array = [];

    var mid = Math.floor(array.length / 2);  

    if (array[mid] === i) {
        return array[mid];
    } else if (array[mid] < i && array.length > 1) {
        return binarySearch(array.splice(mid, Number.MAX_VALUE), i);
    } else if (array[mid] > i && array.length > 1) {
        return binarySearch(array.splice(0, mid), i);
    } else {        
        return -1;
    }
}

Ejemplo:

array = [1,2,3,4,5,6,7,8,9,10];

binarySearch(array, 2) --> Devolvería 1 ya que array[1] = 2 (Donde 2 sería el número sobre el cuál queremos saber su posición en el array)

¿Cuál es el error?

¿Alguien me podría explicar? Por favor.

2
  • @padaleina Ejemplo: // array = [1,2,3,4,5,6,7,8,9,10]; // binarySearch(array, 2) --> Devolvería 1 ya que array[1] = 2 // [Donde 2 sería el número sobre el cuál queremos saber su posición en el array]
    – Pabmena
    Commented el 13 ago. 2021 a las 13:27
  • @padaleina no se como editar el codigo soy nuevo x aca
    – Pabmena
    Commented el 13 ago. 2021 a las 13:29

3 respuestas 3

2

Es correcto que te dé -1. Fíjate que tienes array definida 2 veces y el scope de ambas variables array es distinto. Mas allá de eso, luego de la segunda llave defines una variable array le asignas un array vacío. Luego le asignas a mid el valor de ese calculo que te da 0 porque la longitud de array es 0 y 0 dividido cualquier número es 0. Y luego vienen los ifs.

Preguntas, si array[0] es igual al valor que tiene i...cualquiera sea el valor de i, eso es falso porque array[0] es nulo... y así todos los ifs hasta que cae en el return -1.

No sé la lógica de tu método pero pruébalo así:

var binarySearch = function (array, i) {
    var mid = Math.floor(array.length / 2);
    if (array[mid] === i) {
      return array[mid];

    } else if (array[mid] < i && array.length > 1) {
      return binarySearch(array.splice(mid, Number.MAX_VALUE), i);

    } else if (array[mid] > i && array.length > 1) {
      return binarySearch(array.splice(0, mid), i);
    } else {
      return -1;
    }
}

Espero te sirva.

2
  • × Debe devolver 1 para el arreglo [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] si busca el 2 (4 ms) × Debería devolver 4 para el arreglo [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] si busca el 5 (3 ms) √ Debería devolver -1 si no encuentra el valor buscado en el arreglo (3 ms)
    – Pabmena
    Commented el 13 ago. 2021 a las 13:21
  • me falla en los 2 primeros test. igual como el codigo q subi primero. debe ser un error minimo que me cambia los numeros,, me no me doy cuenta cual es
    – Pabmena
    Commented el 13 ago. 2021 a las 13:22
1

Hay algunos problemas con tu código:

  • No debes volver a definir el arreglo dentro de la función
  • Al encontrar una coincidencia, devuelves el valor buscado y no el índice return array[mid];
  • Se necesita agregar una variable extra a la función para identificar el índice real, porque en llamadas recursivas se reciben trozos del arreglo original, por ejemplo, al buscar 8, en [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] en la llamada recursiva recibirás [6, 7, 8, 9, 10] y el índice original se pierde
  • Finalmente, deberías usar Array.slice() al obtener cada nuevo segmento para no modificar el arreglo original

Cambié los nombres de las variables internas para que tengan un poco más de sentido y te den la idea de lo que realmente se está haciendo.

// Se van a recibir partes del arreglo, es necesario mantener un índice
let binarySearch = (haystack, needle, index = 0) => {
    // Evitar analizar si el arreglo no tiene elementos
    if(haystack.length == 0) {
        return -1;
    }
    let mid = Math.floor(haystack.length / 2);
    if(haystack[mid] == needle) {
        // Hay coincidencia, se debe devolver índice "real", no valor
        return mid + index;
    } else if(haystack[mid] < needle && haystack.length > 1) {
        // Se incrementa el índice, porque se está enviando la parte "superior" del arreglo
        return binarySearch(haystack.slice(mid, Number.MAX_VALUE), needle, index + mid);
    } else if(haystack[mid] > needle && haystack.length > 1) {
        // El índice se mantiene porque se envía la parte "inferior" del arreglo
        return binarySearch(haystack.slice(0, mid), needle, index);
    }
    return -1;
};

let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(binarySearch(arr, 2)); // 1
console.log(binarySearch(arr, 4)); // 3
console.log(binarySearch(arr, 8)); // 7
console.log(binarySearch(arr, 12)); // -1

2
  • gracias efectivamente ahi funciono !!! abrzo grande @Triby
    – Pabmena
    Commented el 13 ago. 2021 a las 17:21
  • @Pabmena, si se resolvió el problema, no olvides marcar la respuesta como aceptada, así otros usuarios con problemas similares sabrán que esto puede servirles.
    – Triby
    Commented el 13 ago. 2021 a las 17:24
0

El problema está en que estás declarando una nueva variable array vacía al inicio de tu función, entonces tú array siempre está vacío.

var array = [];

Mi consejo es que intentes utilizar nombres más específicos, algo como: orderedArray. Como es una búsqueda binaria tiene como pre-condición un conjunto ordenado.

Saludos.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.