Khan academy Algorithm: Binary Search Solution

Question

I was working towards algorithms in khan academy : https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/p/challenge-binary-search Most of the code below results in -1 ? Why is that? So Binary Search Wont work Efficiently ?

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

for(var i=0;i<primes.length;i++){
    var result = doSearch(primes,primes[i]);
    console.log("Found prime at index of " + primes[i] +" @ " + result);    
}

Results:

Found prime at index of 2 @ 0
Found prime at index of 3 @ -1
Found prime at index of 5 @ 2
Found prime at index of 7 @ 3
Found prime at index of 11 @ -1
Found prime at index of 13 @ 5
Found prime at index of 17 @ 6
Found prime at index of 19 @ -1
Found prime at index of 23 @ 8
Found prime at index of 29 @ -1
Found prime at index of 31 @ 10
Found prime at index of 37 @ -1
Found prime at index of 41 @ 12
Found prime at index of 43 @ 13
Found prime at index of 47 @ -1
Found prime at index of 53 @ 15
Found prime at index of 59 @ 16
Found prime at index of 61 @ -1
Found prime at index of 67 @ 18
Found prime at index of 71 @ 19
Found prime at index of 73 @ -1
Found prime at index of 79 @ 21
Found prime at index of 83 @ -1
Found prime at index of 89 @ 23
Found prime at index of 97 @ -1

What am i missing?

The problem here isn't with efficiency, but correctness.

Scott Hunter
– Scott Hunter

2015-06-01 10:42:46 +00:00
Commented Jun 1, 2015 at 10:42 — Scott Hunter
– Scott Hunter, Commented Jun 1, 2015 at 10:42

Evan Knowles · Accepted Answer · 2015-06-01 07:20:39Z

You are terminating the loop too early - min == max is a valid condition.

Change your loop to

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

}

I get an output of

VM153:30 Found prime at index of 2 @ 0
VM153:30 Found prime at index of 3 @ 1
VM153:30 Found prime at index of 5 @ 2
VM153:30 Found prime at index of 7 @ 3
VM153:30 Found prime at index of 11 @ 4
VM153:30 Found prime at index of 13 @ 5
VM153:30 Found prime at index of 17 @ 6
VM153:30 Found prime at index of 19 @ 7
VM153:30 Found prime at index of 23 @ 8
VM153:30 Found prime at index of 29 @ 9
VM153:30 Found prime at index of 31 @ 10
VM153:30 Found prime at index of 37 @ 11
VM153:30 Found prime at index of 41 @ 12
VM153:30 Found prime at index of 43 @ 13
VM153:30 Found prime at index of 47 @ 14
VM153:30 Found prime at index of 53 @ 15
VM153:30 Found prime at index of 59 @ 16
VM153:30 Found prime at index of 61 @ 17
VM153:30 Found prime at index of 67 @ 18
VM153:30 Found prime at index of 71 @ 19
VM153:30 Found prime at index of 73 @ 20
VM153:30 Found prime at index of 79 @ 21
VM153:30 Found prime at index of 83 @ 22
VM153:30 Found prime at index of 89 @ 23
VM153:30 Found prime at index of 97 @ 24

Scott Hunter · Accepted Answer · 2015-06-01 10:41:23Z

2

Suppose your list had just 2 primes, and you search for the larger. Your loop will test against the smaller, fail, and set min to be the same as max, so the loop will terminate before ever checking that value.

Your loop guard should be min <= max.

answered Jun 1, 2015 at 10:41

Scott Hunter

50k12 gold badges64 silver badges107 bronze badges

Collectives™ on Stack Overflow

Khan academy Algorithm: Binary Search Solution

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related