Given a set s of n numbers, x1, x2, . . xn, and an integer k, 1 ≤ k ≤ n, design an algorithm to find y1, y2 . . yk−1 (yi ∈ s and yi ≤ yi+1) such that they induce partitions of s of roughly equal size. namely, let si = {xj |yi−1 ≤ xj ≤ yi} be the i − th partition and assume y0 = −∞ and yk = ∞. the number of elements in si is bn/kc or bn/kc + 1.
note: if k = 2 then it suffices to find the median.

Suppose there is a relation r(a, b, c) with a b+-tree index with search keys (a, b).1. what is the worst-case cost of finding records satisfying 10 < a < 50 using this index, in terms of the number of records n1, retrieved and the height h of the tree? 2. what is the worst-case cost of finding records satisfying 10 < a < 50 and 5 < b < 10 using this index, in terms of the number of records n2 that satisfy this selection, as well as n1 and h defined above? 3. under what conditions on n1 and n2, would the index be an efficient way of finding records satisfying the condition from part (2)?