Khan Academy Binary Search Algorithm step 3 correct, but not passing.

Question

I'm working through the Khan Academy Binary Search problem and step three is asking for some basic additions to "...help visualize how long the search takes."

The prompt asks to "...add a println() statement that displays the total number of guesses it takes to find the result. Your function should only print the total number of guesses when it has found the target. Your function shouldn't be printing the number of guesses every loop."

I have done this successfully with a incrementing counter and a println() with that variable. Running the code works perfectly, however, the Khan Academy pre-built environment will not let me past this step. Is there another way they are expecting?

Code here:

/* Returns either the index of the location in the array,
  or -1 if the array did not contain the targetValue */

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

    while(min <= max){
        guess = Math.floor((min + max) / 2);
        println("You guessed " + guess);
        if(array[guess] === targetValue){
            println(guessTotal);
            return guess;
        }
        else if (array[guess] < targetValue){
            min = guess + 1;
        }
        else{
            max = guess -1;
        }
        guessTotal ++;
    }
    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);

Note: I also tried adding returning an array with the guess and guessTotal, then printing them from the result. That also did what they asked, but did not pass either.

From what you state it sounds like this is a question for Khan Academy. I have no idea what their test cases look like. — David Hoelzer, May 21 '15 at 19:07

score 6 · Answer 1 · answered Mar 11 '16 at 15:45

Here right answer

 /* Returns either the index of the location in the array,
  or -1 if the array did not contain the targetValue */
var doSearch = function(array, targetValue) {
    var min = 0;
    var max = array.length - 1;
    var guess;
    var guessTotal = 0;
     while(min <= max) {
        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);

AwiCodes · Answer 2 · 2016-06-17T03:29:41.990

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

OMIT 1: You're already printing at the bottom after you run the function
OMIT 2: You're already setting your counter with guessTotal++ below;
OMIT 3: It appears here like you're trying to also print your counter which you don't need to do.

If you omit those 3 lines, your code should now run properly.

For the next step in Khan Academy's challenge (which I realized afterwards), your code is fine except for your counter that should start at 1:

var guessTotal = 1;
or
println(guessTotal + 1 );

Hope this was helpful.

Vinod · Answer 3 · 2015-05-21T21:02:32.107

1

Replace var guessTotal = 0 with var guessTotal = 1 or you can keep var guessTotal = 0 and increment it right after you get into while loop.

Basically you have to satisfy their condition

From Khan Academy - Note: A binary search for the target value 41 on the array primes requires 1 guess.

Your code returns 0 for the above condition

edited May 21 '15 at 21:02

answered May 21 '15 at 20:45

Vinod

101
1
10

Khan Academy Binary Search Algorithm step 3 correct, but not passing.

3 Answers3