CODEWITHSUNDEEP
javascriptbinary-search
Marcooz2007
Marcooz2007

Reputation: 335

Javascript Binary Search algorithm unable to find number in the list

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

Upvotes: 1

Views: 453

Answers (4)

Nina Scholz
Nina Scholz

Reputation: 386620

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

Upvotes: 1

Sarabadu
Sarabadu

Reputation: 597

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.

Upvotes: 1

Alberto
Alberto

Reputation: 12939

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

Upvotes: 3

Jonathan Hamel
Jonathan Hamel

Reputation: 1393

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.

Upvotes: 1

Related Questions