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 trialSeokhyun Wie
Full Stack JavaScript Techdegree Graduate 21,606 PointsJavaScript 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.log
s so that you can visualize how arrays are forming step by step. You can play with changing target numbers at the bottom. Happy Coding!
2 Answers
Mike Straw
7,100 PointsSince 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
Full Stack JavaScript Techdegree Graduate 21,606 PointsGia 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 . Thanks for your insight.
Gia Chan
Full Stack JavaScript Techdegree Student 2,762 PointsThanks for your sharing. I just got into this two days ago too, keep going and enjoy!
Gia Chan
Full Stack JavaScript Techdegree Student 2,762 PointsGia Chan
Full Stack JavaScript Techdegree Student 2,762 Pointsbut .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);
} }