written 8.5 years ago by | • modified 8.5 years ago |
Similar questions
Draw and explain control graph for binary search function.
Marks: 10
Year: Dec 2012, June 2013
written 8.5 years ago by | • modified 8.5 years ago |
Marks: 10
Year: Dec 2012, June 2013
written 8.5 years ago by |
intbinarysearch (int x, int V[ ], int n)
{
int low, high, mid ;
low= 0;
high = n-1 ;
while (low< = high)
{ mid = ( low <= high) / 2 ;
if( x < V[mid] )
high = mid – 1;
else if (x > V[mid])
low = mid +1 ;
else
return mid ;
}
return -1 ;
}
Figure : Control flow graph for binary search program
In the above Control Flow Graph for a Binary Search Routine the input array V is assumed to be sorted in ascending order, n is the array size and X is the index of an element in the array V.
If X is not found in the array, the routine is supposed to return -1.
Test cases should be derived so that all of these paths in the control flow graph are executed.
Preconditions: Array has at least one element
Postconditions: Element is not in the array, and return value is -1, or Element is in the array at the returned position
If all of these paths are executed we can be sure that every statement in the method has been executed at least once and that every branch has been exercised for true and false conditions. The number of tests that you need to ensure that all paths through the program are exercised is the same as the cyclomatic complexity of the code fragment that is being tested.