CODEWITHSUNDEEP
javascriptalgorithmbinary-searchkhan-academy
desicoder
desicoder

Reputation: 11

Khan Academy Algorithms Challenge: Binary Search

The following is a simple binary search code written in JS. This code is returning -1 whereas it should return 20. Things I have done after looking around a bit:

  1. Replaced "while(min < max)" to "while(min <= max)" would pop up an error on KhanAcademy.

  2. I have used the Math.floor function, which for some reason pops an error "env.Math.floor is not a function" so instead used the "Math.round".

    var doSearch = function(array, targetValue) {
      var min = 0;
      var max = array.length - 1;
      var guess;
      while (min < max) {
        guess = Math.round((max + min) / 2);
        if (array[guess] === targetValue) {
          return guess;
        } else if (array[guess] < targetValue) {
          min = guess + 1;
        } else {
          max = guess - 1;
        }
      }
      return -1;
    };
    var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
    var result = doSearch(primes, 73);
    console.log("Found prime at index " + result);
     //print (primes[]);
     //Program.assertEqual(doSearch(primes, 73), 20);

Upvotes: 1

Views: 1576

Answers (5)

Abd-ElRhman El Shorbagii
Abd-ElRhman El Shorbagii

Reputation: 3

This is the full right Solution for the 4 phases.

var doSearch = function(array, targetValue) {
var min = 0;
var max = array.length - 1;
var guess;
var guessTotal = 0;

while(max >= min){
    guess = Math.floor((max + min) / 2);
    println(guess);
    guessTotal++;
    if(array[guess] === targetValue){
        println(guessTotal);
        return guess;
    }
    else if(array[guess] < targetValue){
        min = guess + 1;
    }
    else{
        max = guess - 1;
    }
}
return -1;
};

var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 
    41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];

var result = doSearch(primes, 73);
println("Found prime at index " + result);

Program.assertEqual(doSearch(primes, 73), 20);
Program.assertEqual(doSearch(primes, 79), 21);
Program.assertEqual(doSearch(primes, 83), 22);

Upvotes: 0

crushwan
crushwan

Reputation: 1

strong text use (min <= max) 

var doSearch = function (array, targetValue) {
    var min = 0;
    var max = array.length - 1;
    var guess;
    while (min <= max) {
        guess = Math.floor((max + min) / 2);
        
        if (array[guess] === targetValue) {
            return guess;
        }
        else if (array[guess] < targetValue) {
            min = guess + 1;
        }
        else {
            max = guess - 1;
        }
    }
    return -1;
};

var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 
        41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];

var result = doSearch(primes, 73);
console.log("Found prime at index " + result);

Upvotes: 0

Nina Scholz
Nina Scholz

Reputation: 386654

I suggest to change the min rps max value to guess at the assignment of the new values.

Additionally I suggest to change Math.round to Math.floor.

(Small hint: After a return, the if clause has ended, so no need for else if.)

var doSearch = function (array, targetValue) {
    var min = 0;
    var max = array.length - 1;
    var guess;
    while (min < max) {
        guess = Math.floor((max + min) / 2);
        if (array[guess] === targetValue) {
            return guess;
        }
        if (array[guess] < targetValue) {
            min = guess;
        } else {
            max = guess;
        }
    }
    return -1;
};
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97],
    result = doSearch(primes, 73);

console.log("Found prime at index " + result);

Upvotes: 0

Louren&#231;o Biselli
Louren&#231;o Biselli

Reputation: 59

there is just a small error in your code. You should change the min = guess + 1 to min = guess - 1.

    var doSearch = function(array, targetValue) {
      var min = 0;
      var max = array.length - 1;
      var guess;
      while (min < max) {
        guess = Math.round((max + min) / 2);
        if (array[guess] === targetValue) {
          return guess;
        } else if (array[guess] < targetValue) {
          min = guess - 1;
        } else {
          max = guess + 1;
        }
      }
      return -1;
    };
    var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
    var result = doSearch(primes, 73);
    console.log("Found prime at index " + result);
     //print (primes[]);
     //Program.assertEqual(doSearch(primes, 73), 20);

Upvotes: -1

Canilho
Canilho

Reputation: 1209

It's in min and max calculation. The "+" and "-" signals are reversed.

    var doSearch = function(array, targetValue) {
      var min = 0;
      var max = array.length - 1;
      var guess;
      while (min < max) {
        guess = Math.round((max + min) / 2);
        if (array[guess] === targetValue) {
          return guess;
        } else if (array[guess] < targetValue) {
          min = guess - 1;
        } else {
          max = guess + 1;
        }
      }
      return -1;
    };
    var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
    var result = doSearch(primes, 73);
    console.log("Found prime at index " + result);
     //print (primes[]);
     //Program.assertEqual(doSearch(primes, 73), 20);

Upvotes: -1

Related Questions