HW: Sorting in the daily life

Problem (10 points):

This problem is about a common daily life application of sorting. Specifically, sorting (e.g., QuickSort) is usually done before we want to search for something. For example, bank accounts are always sorted according to the account numbers in order to facilitate searching a particular account on request.

Consider, as shown above, a sorted (in ascending order) list of n numbers (assume n is a power of 2, i.e., n = (2^k) for some positive integer k ). To search for a number x in the list, we can use the following algorithm. Compare x with the number in the middle of the list (i.e., m shown above). If they are equal, then our job is done. If x is smaller than that middle number, then we repeat this search process using just the left half of the list; otherwise, we repeat this search process using just the right half of the list.

(a) Why we can use just the left half of the list if the first comparison tells us that x is smaller than

the middle number?

(b) Please express the above algorithm as a recursive method.

(c) Please give the number of comparisons needed in the worst case. Explain your answer.