Question

C++ Need the step count for this function.

int binarySearch(const int array[], int size, int value) {

int first = 0,

last = size − 1,

middle,

position = −1;

bool found = false;

while (!found && first <= last) {

middle = (first + last) / 2;

if (array[middle] == value)

{

found = true;

position = middle;

} else if (array[middle] > value)

last = middle − 1;

else

first = middle + 1;

}

return position;

}

Answer 1

int binarySearch(const int array[], int size, int value) {

int first = 0, //STEP 1

last = size − 1, //STEP 1

middle,

position = −1;

bool found = false; //STEP 1

//HERE middle is defined by (first+last)/2, in each iteration Hence. By means of time,Hence here STEP (log(N))

while (!found && first <= last) {

if (array[middle] == value)

{

found = true; // STEP 1

position = middle; //STEP 1

} else if (array[middle] > value)

last = middle − 1; //STEP 1

else

first = middle + 1; STEP 1

}

return position; STEP 1

}

/*

STEP CALCULATION

HENCE OVERALLL

STEP1 + STEP1+ STEP1+ STEP (Log(n)) + STEP1+ STEP1+ STEP1+ STEP1+ STEP1

Finally STEP 8 + STEP LOG(N)

eliminating constants , we have

log(n) steps,

Hence with log(n) steps, this algorithm runs,

Also time complexity is O(log(n))

*/