You have N coins. All are the same weight except for one, which is either heavier or lighter than the others. Design an efficient algorithm to identify the counterfeit coin. You are given a weighing scale (not a balance scale, which compares 2 weights!). You know that out of the N coins, one and only one coin is counterfeit (i.e. heavier or lighter than the others), but you don’t know if it’s heavier or lighter.
变种 : Solve the question in the case where you know that the bad coin is heavier than the others.