Reference no: EM133217992

Question: You are interested in finding the median salary in Syracuse City. The city has two towns, Happyville and Sadtown. Each town maintains a database of all of the salaries for that particular town, but there is no central database. Each town has given you the ability to access their particular data by executing queries. For each query, you provide a particular database with a value k such that 1 ≤ k ≤ n, and the database returns to you the kth smallest salary in that town. You may assume the following:

• Each town has exactly n residents (so 2 × n total residents across both towns)

• Every salary is unique (i.e., no two residents, regardless of town, have the same salary)

• We define the median as the nth highest salary across both towns. (a) Design an algorithm that finds the median salary across both towns in θ(log(n)) total queries. (b) Prove that the algorithm finds the correct answer.