Searching algorithm used in switch statement

Question

What is the searching algorithm used in switch statement in C language?

If the cases are not in order still it searches proper case which means it is not a binary search algorithm, can anybody explain?

• user40980: Note, you can see what it actually does by decompiling it (often the -S switch in a compiler). For example: godbolt.org/g/aZPl0l (and be sure to change the compiler version in that link to see how different compilers do it).

Answer 1

Several options:

1. the naive method would be an if else cascade (slow)

2. the compiler can sort the cases behind the scene and then do a binary search (good for disjoint cases)

3. a jump table; only good for sequential cases but very fast.

For string-based switches there is the option of the prefix Trie, a sorted table that can be binary searched or the strings are hashed and used for the cases of a switch against the hash of the input string with a double check in each case.

• user40980: Note that the if/else cascade has some difficulty when you do something like case 1: foo; case 2: bar; break; that can make some cases a bit more difficult to do.
• ratchet freak: @MichaelT then the compiler would just copy the code of case 2 to after case 1 or make it a if cascade with goto endSwitch; for each break.

Answer 2

Generally, switch statements are implemented as Jump Tables. There is no searching involved.

• Doc Brown: Does this not depend on the compiler, the level of optimization and maybe on the set of switch values?
• Telastyn: @DocBrown - I didn't think it did - especially for a language like C that is more aggressive at restricting its legal swtichable values, though ratchet freak's 2nd point is a good one to indicate that jump tables are maybe less ubiquitous than I was led to believe.