The predecessor problem is, given a sorted array a_1, a_2,... a_n and a target x, find the position j of the largest a_j lessthanorequalto x, or return 0 if x is smaller than all elements in the array. Give a version of the binary search algorithm that solves this problem, and prove that it is correct. Say we have an object of some unknown weight w > 1 in grams, an unlimited supply of 1 gram weights, and a balance with two arms, which will tip down the arm with the heavier total amount in it. Show how we can determine [w] i.e., w to within a gram, with at most 2[log w] uses of the balance. The predecessor problem is, given a sorted array a_1, a_2,... a_n and a target x, find the position j of the largest a_j lessthanorequalto x, or return 0 if x is smaller than all elements in the array. Give a version of the binary search algorithm that solves this problem, and prove that it is correct. Say we have an object of some unknown weight w > 1 in grams, an unlimited supply of 1 gram weights, and a balance with two arms, which will tip down the arm with the heavier total amount in it. Show how we can determine [w] i.e., w to within a gram, with at most 2[log w] uses of the balance