Consider the following C program segment. while (first <= last) { if…
2015
Consider the following C program segment.
while (first <= last)
{
if (array[middle] < search)
first = middle + 1;
else if (array[middle] == search)
found = TRUE;
else
last = middle - 1;
middle = (first + last)/2;
}
if (first > last)
notpresent = TRUE;
The cyclomatic complexity of the program segment is_______________.
Attempted by 42 students.
Show answer & explanation
Correct answer: 5
Key idea: Binary search halves the search interval each time we compare the middle element to the search value.
General formula: If n is the number of elements in the current search interval (n = last - first + 1), the maximum number of times the code compares array[middle] to search is floor(log2(n)) + 1.
Illustration for n = 16 elements: each comparison reduces the remaining interval roughly by half:
Start: 16 elements → compare middle (1)
Then: 8 elements → compare middle (2)
Then: 4 elements → compare middle (3)
Then: 2 elements → compare middle (4)
Then: 1 element → compare middle (5)
Therefore, for an initial interval of 16 elements the loop can perform up to 5 comparisons of array[middle] with search. This matches the numeric answer 5.
Note: If the initial interval length differs, compute n = last - first + 1 and use floor(log2(n)) + 1 to get the maximum number of comparisons.