Welcome to the Treehouse Community

Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community! While you're at it, check out some resources Treehouse students have shared here.

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.

Start your free trial

Computer Science Introduction to Algorithms Algorithms in Code Binary Search Implementations

Seokhyun Wie
seal-mask
.a{fill-rule:evenodd;}techdegree seal-36
Seokhyun Wie
Full Stack JavaScript Techdegree Graduate 21,606 Points
Posted by Seokhyun Wie
.a{fill-rule:evenodd;}techdegree seal-36
Seokhyun Wie
Full Stack JavaScript Techdegree Graduate 21,606 Points

JavaScript Recursive Binary Search

const recursive_binary_search = (array, target) => {
    if (array.length == 0) {
        return false;
    } else {
        const midpoint = Math.floor(array.length / 2);
        if (array[midpoint] == target) {
            return true;
        } else {
            if (array[midpoint] < target) {
                const newArray = array.filter((num) => num > array[midpoint]);
                console.log(newArray);
                return recursive_binary_search(newArray, target);
            } else {
                const newArray = array.filter((num) => num < array[midpoint]);
                console.log(newArray);
                return recursive_binary_search(newArray, target);
            }
        }
    }
};

const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const result = recursive_binary_search(numbers, 10);
console.log(result);

I don't see Recursive Binary Search JavaScript version here, but only has plain Binary Search one. For some of you who learned only JS at this point and want to know how it works, you can copy and paste this code and run it. I added a couple of console.logs so that you can visualize how arrays are forming step by step. You can play with changing target numbers at the bottom. Happy Coding!

Gia Chan
seal-mask
.a{fill-rule:evenodd;}techdegree
Gia Chan
Full Stack JavaScript Techdegree Student 2,762 Points
Gia Chan
.a{fill-rule:evenodd;}techdegree
Gia Chan
Full Stack JavaScript Techdegree Student 2,762 Points

but .filter is linear runtime? i think the correct answer is below. function recursive_binary_search(list, target) { if (list.length === 0) { return false; } else { let midpoint = Math.floor(list.length / 2);

if (list[midpoint] === target) {
  return true;
} else {
  if (list[midpoint] < target) {
    return recursive_binary_search(list.slice(midpoint + 1), target);
  } else if (list[midpoint] > target) {
    return recursive_binary_search(list.slice(0, midpoint), target);
  }
}

} }

2 Answers

Mike Straw
Mike Straw
7,100 Points
Mike Straw
Mike Straw
7,100 Points

Since the main Python code was rewritten to account for the cost of array.slice(), I built my recursive_binary_search.js like this:

function recursive_binary_search( list, target, start = 0, end = false ) {
    if ( ! end ) {
        end = list.length - 1;
    }
    if ( start > end ) {
        return false;
    } else {
        mid = Math.floor( ( ( start + end ) / 2 ) );
        if ( target === list[mid] ) {
            return mid;
        } else if ( target < list[mid] ) {
            return recursive_binary_search( list, target, start, mid - 1 );
        } else {
            return recursive_binary_search( list, target, mid + 1, end );
        }

    }
}
Seokhyun Wie
seal-mask
.a{fill-rule:evenodd;}techdegree seal-36
Seokhyun Wie
Full Stack JavaScript Techdegree Graduate 21,606 Points
Seokhyun Wie
.a{fill-rule:evenodd;}techdegree seal-36
Seokhyun Wie
Full Stack JavaScript Techdegree Graduate 21,606 Points

Gia Chan Yeah, I just wanted to code to look similar, but I never thought about that. Here: Medium, I could find some comparisons; however, nothing was mentioned regarding the time-complexity, but also Here: StackOverflow, someone claims that the array.slice() has linear runtime complexity, O(n). I just got into this algorithm course two days ago, so I need some more research on this :sparkles:. Thanks for your insight.