Binary Search Question

When completing Unit 6 Lesson 2, a student asked “How can you do a binary search if you have an even amount of numbers?”
The activity had 7 numbers but what if there were 8?

Use the formula (last index - first index)/2 to determine the center. Since this is an integer division, it will truncate the answer. So, if there are 7 elements, last index is 6, therefore the middle element is at index = (6-0)/2 = 3. If there are 8 elements, the last index is 7, therefore the middle element is at index = (7-0)/2 = 3. has you covered. From the lesson plan:

What @bhatnagars is saying is to just use the smaller one.

In the discussion goal section, we explore the question of which algorithm would you use if you have 1, 5, or 100 items. In the case of 1 input, the sort is mentioned. I would also want to know if the items are already sorted in any case, not just 1. I would also want to know how many times you are going to search for an item. That is because sorting is n log n. You can eat up any savings from binary search if you have to sort first and don’t search a bunch of times.

Here is an App Lab project I created with n, log n, and n log n graphed out. The right graph corner is N. You change N with the buttons. - App Lab Keep in mind these are just trend graphs and comparing them at small N is not that useful.

If it were me I would use linear search for 1 and 5 items. And ask questions about the 100 items before deciding on an algorithm.

You also have to take into account potential bugs in the implementation. One of my first jobs was with the company that makes engines for the cruise missiles. The engineers wrote their own programs to do the math in the designs. I found a bug in a large FORTRAN program. It was supposed to do a least squares approximation. It didn’t do that at all. Choosing a complex algorithm comes with its own set of risks.

Unit 6 Lesson 3 Level 3 is a question that compares several growth trends (big O notation) to each other. I created this - App Lab version to show how those 4 choices grow. Especially to compare 2^n to n^20. Both grow fast.

You can use either version to remix and add your own graphs easily.