I have the following problem:
You have n objects that have identical weight except for one that is a bit heavier than the others. You have a balance scale. You can place objects on each side of the scale and see which collection is heavier.
Goal is to find the heavier object, with the minimum number of weigh.
I know the best algorithm that can solve this problem. Here is the pseudocode:
function findDiffWeight(L[1:n]){
if(L.size == 1) return L[1]
int x = sum(L[1 : n/2])
int y = sum(L[n/2+1 : n])
if(x>y) call findDiffWeight(L[1 : n/2])
if(y>x) call findDiffWeight(L[n/2+1 : n])
}
But I am struggling with finding the lower bound for this problem. I don't think that there can be a better algorithm that can solve this in less than logn
operations.
However how to prove it? Could you give me some idea about finding lower bound for this problem?