Dichotomic search
Encyclopedia
In computer science
, a dichotomic search is a search algorithm
that operates by selecting between two distinct alternatives (dichotomies) at each step. It is a specific type of divide and conquer algorithm
. A well-known example is binary search.
Abstractly, a dichotomic search can be viewed as following edges of an implicit binary tree
structure until it reaches a leaf (a goal or final state). This creates a theoretical tradeoff between the number of possible states and the running time: given k comparisons, the algorithm can only reach O(2k) possible states and/or possible goals.
Some dichotomic searches only have results at the leaves of the tree, such as the Huffman tree used in Huffman compression, or the implicit classification tree used in Twenty Questions
.
Other dichotomic searches also have results in at least some internal nodes of the tree, such as a dichotomic search table for Morse code
. There is thus some looseness in the definition. Though there may indeed be only two paths from any node, there are thus three possibilities at each step: choose one onwards path or the other, or stop at this node.
Dichotomic searches are often used in repair manuals, sometimes graphically illustrated with a flowchart
similar to a fault tree.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, a dichotomic search is a search algorithm
Search algorithm
In computer science, a search algorithm is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots...
that operates by selecting between two distinct alternatives (dichotomies) at each step. It is a specific type of divide and conquer algorithm
Divide and conquer algorithm
In computer science, divide and conquer is an important algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly...
. A well-known example is binary search.
Abstractly, a dichotomic search can be viewed as following edges of an implicit binary tree
Binary tree
In computer science, a binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to...
structure until it reaches a leaf (a goal or final state). This creates a theoretical tradeoff between the number of possible states and the running time: given k comparisons, the algorithm can only reach O(2k) possible states and/or possible goals.
Some dichotomic searches only have results at the leaves of the tree, such as the Huffman tree used in Huffman compression, or the implicit classification tree used in Twenty Questions
Twenty Questions
Twenty Questions is a spoken parlor game which encourages deductive reasoning and creativity. It originated in the United States and escalated in popularity during the late 1940s when it became the format for a successful weekly radio quiz program....
.
Other dichotomic searches also have results in at least some internal nodes of the tree, such as a dichotomic search table for Morse code
Morse code
Morse code is a method of transmitting textual information as a series of on-off tones, lights, or clicks that can be directly understood by a skilled listener or observer without special equipment...
. There is thus some looseness in the definition. Though there may indeed be only two paths from any node, there are thus three possibilities at each step: choose one onwards path or the other, or stop at this node.
Dichotomic searches are often used in repair manuals, sometimes graphically illustrated with a flowchart
Flowchart
A flowchart is a type of diagram that represents an algorithm or process, showing the steps as boxes of various kinds, and their order by connecting these with arrows. This diagrammatic representation can give a step-by-step solution to a given problem. Process operations are represented in these...
similar to a fault tree.