Dichotomic search

In computer science, a dichotomic search is a search algorithm that operates by selecting between two distinct alternatives (dichotomies[1] or polychotomies[2] when they are more than two) at each step.

It is a specific type of divide and conquer algorithm.

[3] 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).

Other dichotomic searches also have results in at least some internal nodes of the tree, such as a dichotomic search table for Morse code.

Dichotomic searches are often used in repair manuals, sometimes graphically illustrated with a flowchart similar to a fault tree.

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 · · · ·