Javascript Binary Search algorithm unable to find number in the list

Question

The following code seems to be unable to find the number in the list. Why might this be?

Trying this with the number to search for as '9' and the array of numbers consisting of numbers between 1-10 inclusively.

array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
count = 0;

function binarySearch(array, number) {
    mid = Math.floor(array.length / 2);
    if (number === array[mid]) {
        return count;
    }

    else if (number < array[mid] && array.length > 1) {
        count++;
        arrayFirst = array.splice(0, array[mid]);
        console.log("Tried: ", array[mid])
        console.log(arrayFirst);
        return binarySearch(arrayFirst, number);
    }

    else if (number > array[mid] && array.length > 1) {
        count++;
        arraySecond = array.splice(array[mid], array.length);
        console.log("Tried: ", array[mid])
        console.log(arraySecond);
        return binarySearch(arraySecond, number);
    }

    else {
        return 'number doesnt exist';
    }


}
console.log(binarySearch(array, 4));

The code is now struggling with finding the number 10 New Edit:

       array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,13,14,15,16,17,18,19,20];
    count = 0;
    
    function binarySearch(array, number) {
        mid = Math.floor(array.length/ 2);
        if (number === array[mid]) {
            return count;
        }
    
        else if (number < array[mid] && array.length > 1) {
            count++;
            arrayFirst = array.splice(0, mid);
            console.log("Tried: ", array[mid])
            console.log(arrayFirst);
            return binarySearch(arrayFirst, number);
        }
    
        else if (number > array[mid] && array.length > 1) {
            count++;
            arraySecond = array.splice(array[mid], mid);
            console.log("Tried: ", array[mid])
            console.log(arraySecond);
            return binarySearch(arraySecond, number);
        }
    
        else {
            return 'number doesnt exist';
        }
    
    
    }
    
    console.log(binarySearch(array, 10));

Your condition includes an undefined variable arr... It's called array — Jonathan Hamel
– Jonathan Hamel, Commented Feb 18, 2020 at 14:32
look at the index, when you do ´Math.floor(array.length/ 2)´ you get 10 but array[10] it the 11th element — Sarabadu
– Sarabadu, Commented Feb 19, 2020 at 11:43

Alberto · Accepted Answer · 2020-02-18 14:34:46Z

3

This:

array = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10;

is not an array, it's interpreted as a list of initialization, like this:

 array = 1, x = 2, y = 3...;

and so your array is just 1, and not the entire list. Also keep in mind that it is Not Recommended to declare a variable without var keyword. It can accidently overwrite an existing global variable. Instead you should use var, let or const based on the use of that variable

Instead, this should be your array:

array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

edited Feb 18, 2020 at 14:34

answered Feb 18, 2020 at 14:29

Alberto

13.1k3 gold badges31 silver badges72 bronze badges

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

2 Comments

Marcooz2007 Over a year ago

aha! silly error, thank you I am new to Javascript! :)

Alberto Over a year ago

no problem, i've added a little bit of explanation. @Marcooz2007

Jonathan Hamel · Accepted Answer · 2020-02-18 14:33:53Z

1

Few pointers here:

Your condition includes an undefined variable arr. You've been using array.
Your array must be array = [1,2,3]
I would suggest to instantiate your variables arrayFirst, mid, arraySecond as const const mid = ... so they are block scoped and not global vars

Edit: Looks like you've modified your arr condition. Please avoid edits as it makes answers irrelevant.

answered Feb 18, 2020 at 14:33

Jonathan Hamel

1,38313 silver badges19 bronze badges

Comments

Sarabadu · Accepted Answer · 2020-02-18 14:44:09Z

1

You are using array.splice(0, array[mid])

array[mid] is the value in the array and you need the quantity of elements to subtract array.splice(0, mid) splice docs

also index start from 0 so your array[mid] is taking the 6th element and not the middle.

answered Feb 18, 2020 at 14:44

Sarabadu

5972 silver badges18 bronze badges

Comments

Nina Scholz · Accepted Answer · 2020-02-18 14:52:15Z

Some changes:

Take counting inside of the function by returning either one or zero or one plus the result of the call with a sub array.
Check length in advance (spelling matters ... arr) and return zero for unrachable values.
Use Array#slice instead of Array#splice (prevent mutation) and take the index, not the value of the item.
Finally return one plus the count of left or right side.

function binarySearch(array, number) {
    console.log(...array);
    var mid = Math.floor(array.length / 2);
  
    if (number === array[mid]) return 1;
    if (array.length <= 1) return 0;

    return number < array[mid]
        ? 1 + binarySearch(array.slice(0, mid), number)
        : 1 + binarySearch(array.slice(mid), number);
}

console.log('count:', binarySearch([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 4));

Collectives™ on Stack Overflow

Javascript Binary Search algorithm unable to find number in the list

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related