Welcome to the Treehouse Community

The Treehouse Community is a meeting place for developers, designers, and programmers of all backgrounds and skill levels to get support. Collaborate here on code errors or bugs that you need feedback on, or asking for an extra set of eyes on your latest project. Join thousands of Treehouse students and alumni in the community today. (Note: Only Treehouse students can comment or ask questions, but non-students are welcome to browse our conversations.)

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and a supportive community. Start your free trial today.

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,594 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

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,059 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,594 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.