If a list has an even number of elements, which is considered the midpoint in binary search?

It's up to you to decide, but your decision should be consistent. When we coded this in class, we set mid = (high + low) // 2, which had the effect of rounding down.

How is binary search faster than linear search if the computer has to look through the list to find the smallest number? Why not just look through the list to find the number?

In binary search, we do just look through the list to find the number --- by checking the midpoint, and then updating our high and low values to continue searching. We also discussed today how selection sort would work, and that algorithm does go through the list to find the smallest number --- but it does a lot more than just find one value in the list. It puts all the values in the list in sorted order!

How do we code to sort a list?

We'll do this next time and on Friday. For now, you have a file with an outline of our plan for how to code selection sort. If you want to, you can try to fill this in yourself and test it on some lists!

Are there ather ways in which linear search can prove efficient?

Sure! Linear search works even if the list is not sorted, which is very useful when we have an unsorted list and just want to find some element. As we'll see over the coming lectures, sorting the items in the list is slower than just using linear search to find one item, so if we just need to find one item and don't want to worry about sorting the list, then linear search is preferable.

How do you do the for loop inside a for loop?

This works the same way that we've been doing if statements inside the body of other if statements:

for i in range(4):
  for j in range(3):
    print(i,j)

The body of the i loop will be executed 4 times. Each time, the entire j loop will be executed 3 times. So the output would be:

0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
3 0
3 1
3 2

Is it really more efficient to do binary search if you have to spend so many steps sorting a list?

You're right that sorting will take much longer than just doing linear search from the start. One reason we might want to sort first, then use binary search, is that if we are doing many searches, then we still only need to sort one time. Once the list is sorted, we can do a lot of binary searches, and each one will be pretty fast! If we had to do the same number of linear searches, the time could add up to many more steps.