Answer to Question #148694 in C++ for ali

Question

) If you have 128 oranges all the same size, color, and weight except one orange is heavier than the rest. Write down a C++ Code/Algorithm to search the heavy orange, in how many steps would you be able to find it out?

Answer 1

Suppose all oranges are enumerated from 0 to 127, then their weights may be put in an array of length 128:

take the first orange weight, compare it to second, if it is heavier, the heavy orange is found, otherwise enter a loop:

int heavy_index;

if (weights[0] > weights[1])
  heavy_index = 0;
else
  for (int i = 1; i < 128; ++i) {
    if (weights[0] < weights[i])
      heavy_index = i;
  }

On average it takes $\approx$ 64 comparisons, while the best case scenario only takes 1 and the worst care takes 128 comparisons