Okay, I've been breaking my head for several days already but found a solution for 7. Your tip helped a lot!
- S - shapeshifter, H - human
- ?x - unknown person number x, * - any person
- ?-? or ?+? - when person on the left was asked "Is next person is Human?" and got Yes(+) or No(-)
We will ask question "Is next person a Human?" in a chain, like some person ask another, then this another person ask yet another and so on. And stop as soon as somebody will say "No". Observation: when the answer is "No", then it could be only
S-*, i.e. there is 100% a shapeshifter in this pair.
There could be multiple situations.
1) We got answer "No" on 4th person or later. ?+?+?+?4-?5 ??. Then the person 4 is H and person 5 is S. Proof(negation): If person 4 is S, then all people before him are also S (because otherwise we will get at least one more "No") but that means we have >=4 shapeshifters which contradicts the setup.
2) We got "No" on 3rd person. ?+?+?3-?4 ???. Then we ask 4 remaining people about person 3. Here could be 2 situations: everybody says "No" -> then he is S. If some say "No" and some "Yes", then he is H. Proof(negation): if he was actually S, then all people before him are also S (see proof above), but that would mean that we already have found 3 shapeshifters, and those 4 remaining people are H, which means they should've answered all "No", thus contradiction => person 3 is H and person 4 is S.
3) Situation when we have "No" on 1st or 2nd person - here approach is the same. Lets assume following situation: ?1+?2-?3 ?4?5?6?7. We know, that there are no more than 3 shapeshifters, and one of them either person 2 or 3. That means among people 1,4,5,6,7 there are at most 2 shapeshifters. Lets ask persons 1,4,5,6,7 same question about person 2. Then majority wins, because shapeshifters are less than half of those people.
Bonus 1: If all people said "Yes", then there are no shapeshifters
EDIT for Bonus 2:
Without loss of generality, let's assume we have
2n + 1 people, among whom at most
Corner case where
x < 0(i.e. we asked already more than half people) its similar to 1) above.
Strategy: ask all remaining
n+x people question "Is this person a Human?" about the one who gave us "No" answer. Observation: There are at most
n-1 shapeshifters among the remaining people and thus at least
x+1 humans. Here could be couple of situations:
1) Everybody said "No", except maybe
x people who said "Yes". Then target person is S, because we know there are at least
x+1 humans, so they all answered "No".
2) If we got more than
x "Yes" answers. Then target person is H. Proof(negation): If target was S, then all people before him are also S (
n-x people) and thus there are at most
x shapeshifters among the remaining people. But that would mean that only those
x shapeshifters could've said "Yes", although we have more than
x "Yes" answers. Contradiction!