Peer-graded Assignment: Binary Search /AN

Question #1. A city planner would like to know the change in crime rate for Kensington. Using linear search to find it in the list, she would first look at Bella Vista, then Center City, then Chestnut Hill, etc. and compare each to “Kensington” before finally finding it after six comparisons. If she were instead to use binary search, which entries in the list would she need to compare to “Kensington” before finding it?

Your answer needs to be a little bit longer. Write a few sentences to complete your assignment.
Question #2. Now the city planner would like to see the change in population for Roxborough. Using binary search, which entries in the list would she need to compare to “Roxborough” before determining it’s not there?

Question #3. In the previous lesson, we saw that binary search requires fewer comparisons than linear search in the worst case. However, there are some cases for which linear search is more efficient. For which neighborhoods in the listing above would linear search require fewer comparisons than binary search?
Hint: for each neighborhood in the listing, calculate the number of steps it would take to find it using linear search, then calculate the number of steps it would take to find it using binary search.

Question #4. For the 15 neighborhoods in the listing above, what is the average number of comparisons required to find an element using linear search? Binary search?

Question #5. By now you should be convinced that binary search requires fewer comparisons than linear search in both the worst case and the average case. However, keep in mind that binary search assumes that the elements are already in sorted order; if they’re not sorted, then it would take time to sort them before applying binary search, and sorting is a slow operation.
Whereas the number of operations in the worst case to conduct binary search on a collection of N items is approximately log2N, the number of operations required to sort N items is Nlog2N, i.e., the value of N times its base-2 logarithm.
Assume you have an unsorted collection of N = 15 items, and you know you will need to make at least 10 searches and are concerned about the worst case. How would you determine whether it would be better to conduct 10 linear searches, or if it would be better to first sort the elements (which you only need to do once) and then conduct 10 binary searches?
In making this decision, follow these steps:
1. First, calculate the number of operations it would require to conduct 10 linear searches in the worst case.
2. Then, calculate the number of operations it would require to sort the elements once; for simplicity, round log215 up to 4.
3. Last, calculate the number of operations it would require to conduct 10 binary searches in the worst case.
4. Use the results of these three calculations to determine the answer.
Show the results of your calculations for steps 1-3 and then explain your answer in step 4.