lundi 15 août 2016

Example inputs that expose binary search bugs

I'm looking for example inputs of sorted lists that expose common bugs in implementations of binary search.

Off-by-one errors are common due to which way you round the division, and different inclusive and exclusive ranges.

Some corner cases that I have thought to check are:

  • Empty lists
  • Lists of size 1
  • Lists with lots of duplicate items

Can you think of test cases that will expose other common mistakes?


I read this other article which talks about common binary search implementation mistakes, and has some good references for reading about them.

I'm looking for specific test cases, however, that people may have used to find bugs in their own code, or in students'/applicants' code.

Aucun commentaire:

Enregistrer un commentaire