Jump Tables / Binary Search

[hediet]

If we have code like that:

if (x == 10) { ... } // 1 test needed
else if (x == 11) { ... } // 2 tests needed 
else if (x == 50) { ... } // 3 tests needed 
else if (x == 100) { ... } // 4 tests needed
else if (x == 111) { ... } // 5 tests needed
else if (x == 200) { ... } // 6 tests needed
// avg: 3.5 tests needed on average, 6 on worst

We could optimize it to:

if (x < 50) {
   if (x == 10) { ... } // 2 tests needed
   else if (x == 11) { ... } // 3 tests needed
} else {
  if (x < 111) {
   if (x == 50) { ... } // 3 tests needed
   else if (x == 100) { ... } // 4 tests needed
  }
  else {
   if (x == 1111) { ... } // 3 tests needed
   else if (x == 200) { ... } // 4 tests needed
  }
}
// avg: 3.17 tests needed on average, 4 on worst

We could even use jump tables if the values are close enough together.