Binary Search Heavier Ball

Given a line of balls, of which one is heavier and all others are the same.
Also, given a function called balance, which works on an array and tells whether the front part or back part is heavier.

Problem: find the heavier ball.

Thinking: it is natural to consider binary search approach. Yes, and it is also efficient with \(O(\log n)\) complexity in time. But there are some subtle problems with the function "balance". This function works like a scale and can only tell which side is heavier. If the heavier side has more balls than the other, we don't know whether this is due to the extra ball or due to the heavier ball. Hence, if we want the function "balance" to work well in this problem, extra energy is needed to guarantee that the balls on each side are equal in terms of number.

Assume the prototype of balance function is
int balance(int A[ ], int l, int r, int p);
The array A represents the array of balls to be balanced, where l is the left end of the array, r is the right end of the array, and p is the partition point where l, l+1, ..., p will be seen as the front part, and p+1, p+2, ..., r the back part. The return value can be 1, -1, or 0. 1 means front part is heavier, -1 means back part is heavier, and 0 means front part and back part weight the same.

Based on this, we can have following solution (code):

To solve the original problem, we need call searchHeavier(A,0,n-1) (assuming there are n balls).

The code above was a recursive function. It's easy to convert it to an iterative version (not shown here).

More thinking about this problem:
If we don't know for sure there is a ball heavier than all other balls. In other words, there is at most one ball which is heavier and all other balls are the same. In this case, only one change need be made to above code: is the remaining ball really heavier? The modified code is as below: