7.3 Binary search strategy

7.3 Binary search strategy

7.3.1 Binary search assumptions

The binary search strategy is analogous to the binary search algorithm taught in introductory data structures or algorithms classes. It works quickly because when it’s applicable, it converges on a solution in time proportional to the logarithm of the number of code segments under scrutiny.

This strategy assumes that the code segments under investigation have some linear ordering. The statements, code blocks, or loop nests in a procedure can be ordered according to the lexical order in which they appear in the program text. The procedures in a program can be ordered by topologically sorting the call graph of the program.

A code block is a group of sequentially executed statements with a single exit point. Literature on compilers often refers to these as basic blocks.

A graph consists of a set of nodes and a set of edges. A topological sort of a directed graph is a listing of the nodes such that if one node directly or indirectly precedes another node in the graph, the first node is listed before the second node in the listing.

7.3.2 Binary search control structure

The next code sample shows the control structure for the binary search strategy.

 Set S to the set of all code segments in question  Do while S has more than one element       Split the set S into two subsets, L and R,           of the same size      Determine in which of the two subsets the problem           first occurs      Set S to the offending subset  End-do  The remaining element is the code segment that contains the bug