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 Recursive Binary Search

Does this video make a mistake or am I misunderstanding the recursive call?

In the example, we have an array [0,1,2,3,4,5,6,7,8] with a length of 9 and I set a target of 8. We check the list is not empty (true) and then set our midpoint equal to Math.floor(list.length / 2) which will evaluate to 4 - correct?

4 is not equal to 8 and 4 is less than our target 8. As a result we call recursiveBinarySearch(list, target) again with two arguments - our new list and target of 8. Pasan says our new list is has 3 values, [6,7,8] but does our list not in fact have 4 values [5,6,7,8] as we remove elements [0,1,2,3,4]? I am a little confused and wonder if this is a mistake or I have misunderstood something.

I think both approaches still work. For example, Pasan explains we calculate the new length of [6,7,8] which is equal to 3 and subsequently divide 3 by 2 = 1.5. We then floor 1.5 which means is 1. Our midpoint = 1. This will select the element at index 1 which is [6, 7, 8].

With my approach I calculate the new length of [5, 6, 7, 8] which is equal to 4 and divide 4 by 2 = 2. There is nothing to floor in this example. Our midpoint = 2. This will select the element at index 2 which is still 7. [5, 6, 7, 8].

Have I missed something here?

1 Answer

Chris Freeman
MOD
Chris Freeman
Treehouse Moderator 67,636 Points

Hey Kit Howlett you are correct! The graphic running of the code clearly has the list [5, 6, 7, 8] as the first recursive call as shown by the highlighted numbers. The audio however says this list contains "6, 7, and 8".

The cause may be due to some version confusion between showing the code implementation (where the example data is 1-based [1, 2, 3, 4, 5, 6, 7, 8] — length 8) and the graphic example (where the example data is 0-based [0, 1, 2, 3, 4, 5, 6, 7, 8] — length 9).

Flagging for feedback.