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

Answer:

#include <iostream>

using namespace std;

void Search_heavy_orange(int arr[], int l, int r, int x)

{

int count = 0, m = 0;

while (l <= r) {

 m = l + (r - l) / 2;

 // Check if x is present at mid

 if (arr[m] == x) {

  count++;

 }

 // If x greater, ignore left half

 if (arr[m] < x) {

  l = m + 1;

  count++;

   

 }

 

 // If x is smaller, ignore right half

 else {

  r = m - 1;

  count++;

 }

}

cout << "............For Worst Case......." << endl;

cout << "Orange with heavy weight is present at index " << m << endl;

cout << "Total number of step performed : " << count << endl;

}

int main()

{

// Assuming each orange is 100 gm and the weight of heavy

// orange is 150 gm

int orange_weight[128];

for (int i = 0; i < 127; i++) {

 orange_weight[i] = 100;

}

// At worst case the heavy orange should be at last position

// inside the basket : 127

orange_weight[127] = 150;

// We will pass array , start index , last index and the search element

// as the parameters in the function Search_heavy_orange

Search_heavy_orange(orange_weight, 0, 127, 150);

return 0;

}

Explanation: