How to create a binary search with recursion

Tags: , , ,



I am attempting to write a “binary search” which I’ve never done before. The code below does not work when the value searched for is 6 or 2 and I want to know what I am doing wrong and how to remedy it.

EDIT

To explain what it is suppose to do (based on my understanding) a binary search requires that an array is already sorted, it then looks for the mid-point index of an array. For example, if an array had nine indexes (0-8)the the mid point would be index 4.

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];

The algorithm then determines if that mid point has a higher or lower value than the number you are searching for. All elements on the side of the array that does not contain the searched for number and that exist before the midpoint value simply get removed. If the search for value is 8 then the result would be:

[ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
array midpoint value: 5
[ 5, 6, 7, 8, 9 ]
array midpoint value: 7
[ 7, 8, 9 ]
array midpoint value: 8

Code

//_________________________________________________BEGIN notes

    // Step 1. Get length of array 
    // Step 2. Find mid point
    // Step 3. Compare if mid point is lower or higher than searched number
    // Step 4. lop off unneeded side
    // Step 5. go to step 1
//_________________________________________________END notes

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 44, 55];

function getMidPoint(arr, searchNumb) {
    var length = arr.length;
    var midPoint = Math.floor(length / 2);
    var newArr = arr;
    console.log(arr);
    console.log("array midpoint value: " + arr[midPoint]);

    if (arr[midPoint] > searchNumb) {

        var newArr = arr.slice(0, arr[midPoint]);
        return getMidPoint(newArr, searchNumb);

    } else if (arr[midPoint] < searchNumb) {

        var newArr = arr.slice(midPoint, arr.length);
        return getMidPoint(newArr, searchNumb);

    } else {
        return arr
    }
}

Answer

  1. You are slicing it wrong.

Use this code:

//_________________________________________________BEGIN notes

    // Step 1. Get length of array 
    // Step 2. Find mid point
    // Step 3. Compare if mid point is lower or higher than searched number
    // Step 4. lop off unneeded side
    // Step 5. go to step 1
//_________________________________________________END notes

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 44, 55];

function getMidPoint(arr, searchNumb) {
    var length = arr.length;
    var midPoint = Math.floor(length / 2);
    var newArr = arr;
    console.log(arr);
    console.log("array midpoint value: " + arr[midPoint]);

    if (arr[midPoint] > searchNumb) {

        var newArr = arr.slice(0, midPoint);
        return getMidPoint(newArr, searchNumb);

    } else if (arr[midPoint] < searchNumb) {

        var newArr = arr.slice(midPoint + 1, arr.length);
        return getMidPoint(newArr, searchNumb);

    } else {
        return midPoint;
    }
}
  1. Also, if the search element is not in array, this will go on infinitely. Add a base case for that too.


Source: stackoverflow