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?

Alane

@JoachimPileborg What do you mean by are you sure? And why am i down voted? i was following this fiddle jsfiddle.net/7zfph6ks – Alane

@JoachimPileborg Doesn't it? It seems to. – Soprano

@JoachimPileborg Is it so? Can you point me a right expression for taking average? – Alane

I'm apparently not awake yet. Sorry for the confusion. – Sexist

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

Answer 1

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

Soprano

Answer 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.

Yalonda