Dichotomic Search on:
[Wikipedia]
[Google]
[Amazon]
In
Python Program for Binary Search (Recursive and Iterative)Binary Search
Search algorithms
In computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, a dichotomic search is a search algorithm
In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the Feasible region, search space of a problem do ...
that operates by selecting between two distinct alternatives (dichotomies or polychotomies when they are more than two) at each step. It is a specific type of divide and conquer algorithm
In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved dir ...
. A well-known example is binary search
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the m ...
.
Abstractly, a dichotomic search can be viewed as following edges of an implicit binary tree
In computer science, a binary tree is a tree data structure in which each node has at most two children, referred to as the ''left child'' and the ''right child''. That is, it is a ''k''-ary tree with . A recursive definition using set theor ...
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(2''k'') possible states and/or possible goals.
Some dichotomic searches only have results at the leaves of the tree, such as the Huffman tree
In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code is Huffman coding, an algorithm developed by ...
used in Huffman coding
In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code is Huffman coding, an algorithm developed by ...
, or the implicit classification tree
Classification chart or classification tree is a synopsis of the classification scheme, designed to illustrate the structure of any particular field.
Overview
Classification is the process in which ideas and objects are recognized, differentia ...
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
Morse code is a telecommunications method which Character encoding, encodes Written language, text characters as standardized sequences of two different signal durations, called ''dots'' and ''dashes'', or ''dits'' and ''dahs''. Morse code i ...
. 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
A flowchart is a type of diagram that represents a workflow or process. A flowchart can also be defined as a diagrammatic representation of an algorithm, a step-by-step approach to solving a task.
The flowchart shows the steps as boxes of v ...
similar to a fault tree
Fault tree analysis (FTA) is a type of failure analysis in which an undesired state of a system is examined. This analysis method is mainly used in safety engineering and reliability engineering to understand how systems can fail, to identify the ...
.
See also
*Binary search algorithm
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the ...
External links
Python Program for Binary Search (Recursive and Iterative)
Search algorithms
References