Can't you easily reduce this to a compatible problem though?

Let's say you have the set of foods you suspect: red blue green yellow brown purple

You construct an ordered set from this by making the elements sets of foods such that each set is the one to its left plus any one more entry, the leftmost set is the empty one, and the rightmost is the one containing all your suspects:

{}, {red}, {red, blue}, {red, blue, green} .... {red, blue, green, yellow, brown}, {red, blue, green, yellow, brown, purple}

Now a check operation means eating the elements in the current set, if you get sick you go half way to the left border and update the right one, if you don't get sick you go half way to the right border and update the left one.

You should end up with the smallest set that makes you sick. Subtract the set to the left of it and you have the food that makes you sick left over.