Given a sorted array- 8 13 17 26 44 56 88 97. Using binary search method find the element 88. show the contents of high low and mid at each step?

Answer 1

The array has eight elements indexed 0 to 7. The middle element will be found at index (0+7)/2=3. Element 3 has the value 26, which is smaller than 88, so 88 must reside in the array starting at index 4 ending at index 7.

The array has four elements indexed 4 to 7. The middle element can be found at index (4+7)/2=5. Element 5 has the value 56, which is smaller than 88, so 88 must reside in the array starting at index 6 ending at index 7.

The array has two elements indexed 6 to 7. The middle element can be found at index (6+7)/2=6. Element 6 has the value 88. Thus 88 was found at index 6.

Answer 2

Function definition:

size_t binary_search (const vector& v, const unsigned value)

{

size_t low=0;

size_t high=v.size();

while (low

{

size_t mid = low + ((high-low) / 2);

if (v[mid]==value)

return mid;

if (v[mid]

low = mid + 1;

else

high = mid;

}

return v.size();

}

Test function:

int main()

{

vector A {8, 13, 17, 26, 44, 56, 88, 97};

size_t index = binary_search (A, 88);

assert (index==6);

}

1st iteration of while loop:

low = 0;

high = 8;

mid = 4; // 0 + ((8 - 0) / 2) = 0 + (8 / 2) = 0 + 4 = 4

A[4] is 44 which is less than 88, so low becomes 4 + 1 = 5.

2nd iteration of while loop:

low = 5;

high = 8;

mid = 6; // 5 + ((8 - 5) / 2) = 5 + (3 / 2) = 5 + 1 = 6

A[6] is 88 which is equal to 88 so 6 is returned.

If we search for a value that does not exist, such as 42, the following would occur instead:

1st iteration of while loop:

low = 0;

high = 8;

mid = 4; // 0 + ((8 - 0) / 2) = 0 + (8 / 2) = 0 + 4 = 4

A[4] is 44 which is greater than 42, so high becomes 4.

2nd iteration of while loop:

low = 0;

high = 4;

mid = 2; // 0 + ((4 - 0) / 2) = 0 + (4 / 2) = 0 + 2 = 2

A[2] is 17 which is less than 42, so low becomes 2 + 1 = 3.

3rd iteration of while loop:

low = 3;

high = 4;

mid = 2; // 3 + ((4 - 3) / 2) = 3 + (1 / 2) = 3 + 0 = 3

A[3] is 26 which is less than 42, so low becomes 3 + 1 = 4.

At this point, low is equal to high, so the loop terminates and we return the size of the vector (8). Since there is no element with index 8 (the valid range being A[0] to A[7]), this tells us the value does not exist. We can verify this with the following test function.

int main()

{

vector A {8, 13, 17, 26, 44, 56, 88, 97};

size_t index = binary_search (A, 42);

assert (index==A.size());

}