Khan Academy Algorithms Challenge: Binary Search

Question

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:

Replaced "while(min < max)" to "while(min <= max)" would pop up an error on KhanAcademy.
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);

Nina Scholz · Accepted Answer · 2016-10-12 20:24:47Z

0

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);

edited Oct 12, 2016 at 20:24

answered Oct 12, 2016 at 20:13

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

desicoder Over a year ago

Yes! Thank you for pointing out that small error, the code does produce the intended result but I am still getting an error saying "It looks like you almost have the correct condition on the while loop, but something is still wrong with it." on KhanAcademy

desicoder Over a year ago

1. Let min = 0 and max = n-1. 2. If max < min, then stop: target is not present in array. Return -1. 3. Compute guess as the average of max and min, rounded down (so that it is an integer). 4. If array[guess] equals target, then stop. You found it! Return guess. 5. If the guess was too low, that is, array[guess] < target, then set min = guess + 1. 6. Otherwise, the guess was too high. Set max = guess - 1. 7. Go back to step 2

crushwan · Accepted Answer · 2022-07-09 08:29:35Z

0

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);

edited Jul 9, 2022 at 8:29

answered Jun 16, 2022 at 14:49

crushwan

13 bronze badges

Comments

Abd-ElRhman El Shorbagii · Accepted Answer · 2023-07-10 09:47:26Z

0

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);

edited Jul 10, 2023 at 9:47

answered Jul 10, 2023 at 9:30

Abd-ElRhman El Shorbagii

33 bronze badges

3 Comments

greybeard Over a year ago

What is the main difference to the code in the question?

Abd-ElRhman El Shorbagii Over a year ago

1- the while condition 2- adding math.floor instead of math.round

Community Over a year ago

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.

Canilho · Accepted Answer · 2016-10-12 20:14:29Z

-1

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);

answered Oct 12, 2016 at 20:14

Canilho

1,2178 silver badges15 bronze badges

1 Comment

desicoder Over a year ago

Khan Academy Challenge: Binary Search This is my challenge, I still seem to get an error.

Lourenço Biselli · Accepted Answer · 2016-10-12 20:14:37Z

-1

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);

answered Oct 12, 2016 at 20:14

Lourenço Biselli

594 bronze badges

1 Comment

desicoder Over a year ago

link This is my challenge, I still seem to get an error.

Collectives™ on Stack Overflow

Khan Academy Algorithms Challenge: Binary Search

5 Answers 5

2 Comments

Comments

3 Comments

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

2 Comments

Comments

3 Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related