Sathish
Sathish

Reputation: 2180

Khan academy Algorithm: Binary Search Solution

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?

Upvotes: 8

Views: 16573

Answers (2)

Scott Hunter
Scott Hunter

Reputation: 49813

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.

Upvotes: 2

Evan Knowles
Evan Knowles

Reputation: 7511

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

Upvotes: 14

Related Questions