(a) Describe in words how the binary search algorithm works:
The binary search algorithm searches for the location of a number 
in an ordered list of numbers 
. It first finds the element in the middle of the list (or right below the middle) and compares to this element. If is less than or equal to this middle element, then the algorithm proceeds to search in the same way in the first half of the list. Likewise, if is greater than the middle element, then the algorithm proceeds to search in the same way in the second half of the list. Either way, the algorithm cuts the list in half until there is just one element left on the list. It then compares this element to .
(b) Show each step of the binary search algorithm as it searches for 27 in the following list: {5, 6, 8, 12, 15, 21, 25, 31}.
First step: 
.
Since 
we redefine 
and search the second half of the original list.
Second step: 
.
Since 
, we redefine 
and search the second half of this list.
Third step: 
.
Since 
, we redefine 
.
Last step: Since 
, we exit the loop and compare 
to 
. Since 
, is not on the list and the algorithm returns location = 0.
There were more troubles than I thought there would be with part (a). Many of you seemed to remember how the binary search algorithm works, but your written work was not clear enough or precise enough for me to understand. Just because you’re using words instead of code to describe an algorithm doesn’t mean you can be sloppy. (For example, you need to say explicitly what the input and the output of the algorithm are.) You still need to use complete sentences and correct grammar so that the reader can understand what you’re writing. In math, where there may be several things that you’re trying to say, it’s often helpful to keep your sentences short. I usually try to say only one thing per sentence, so that the reader can focus on one thing at a time. Some of your descriptions used very long run-on sentences and it was very difficult for me to follow.
Part (b) was done well, for the most part. However, it wasn’t always clear how the steps were organized. You can see above how I organized my steps; that’s not the only way to organize them, but it’s a pretty obvious way.