Misplaced Pages

Dichotomic search

Article snapshot taken from[REDACTED] with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Type of search algorithm
This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (December 2014) (Learn how and when to remove this message)
A graphical representation of the dichotomic search table for Morse code. An upward step represents a Dit (.), and a downward step represents a Dah (-). Where one lands indicates the letter for the code.
T – M – – O – – – CH – – – –
Ö – – – ·
G – – · Q – – · –
Z – – · ·
N – · K – · – Y – · – –
C – · – ·
D – · · X – · · –
B – · · ·
E · A · – W · – – J · – – –
P · – – ·
R · – · Ä · – · –
L · – · ·
I · · U · · – Ü · · – –
F · · – ·
S · · · V · · · –
H · · · ·

In computer science, a dichotomic search is a search algorithm 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. 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(2) 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 coding, 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.

See also

External links

References

  1. "dichotomic search". xlinux.nist.gov. Retrieved 2024-05-30.
  2. "polychotomy". xlinux.nist.gov. Retrieved 2024-05-30.
  3. "Binary Search Implementation in Python: A Tutorial | Built In". builtin.com. Retrieved 2023-12-07.
Stub icon

This computer science article is a stub. You can help Misplaced Pages by expanding it.

Categories:
Dichotomic search Add topic