Draw the data flow graph for the Binary Search routine and explain the same.

Mahesh Kariya
Nov 1 · 2 min read

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.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade