1

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?

  • 2
    Note, you can see what it actually does by decompiling it (often the -S switch in a compiler). For example: goo.gl/aZPl0l (and be sure to change the compiler version in that link to see how different compilers do it). – user40980 Dec 12 '14 at 20:07
6

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.

  • 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. – user40980 Dec 12 '14 at 20:00
  • @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. – ratchet freak Dec 12 '14 at 20:03
5

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

  • Does this not depend on the compiler, the level of optimization and maybe on the set of switch values? – Doc Brown Dec 12 '14 at 19:34
  • @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. – Telastyn Dec 12 '14 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.