Divide and Conquer to identify a knight from n people

So I am doing an exercise in which there are $n$ people who are either knight or rogue, more than $\frac{n}{2}$ are knights. You are a princess and would like to marry a knight and do not want to accidentally marry a rogue.

You can select any pair of the $n$ people to make them point out each other's identity. The knight will always tell the truth, while the rogue may or may not. If there are two rogues being interrogated, they may say each other is good to deceive you.

How can I design an efficient algorithm for the princess to find out a knight?

My attempt:

So I can pit one person j against the other $n-1$ persons to find out if j is knight or rogue. There are $k > \frac{n}{2}$ knights, and $r \leq \frac{n}{2}-1$ rogues.

If j is a knight, then he will be pitted against $k-1$ other knights and $r$ rogues. So there are $\geq \frac{n}{2}$ cases in which both say the other person is knight, and there will be $\leq \frac{n}{2} - 1$ cases that at least 1 person is accused of being a rogue.

If j is a rogue, then j will be pitted against $k$ knights and $r-1$ other rogues, resulting in $k$ cases of at least one rogue accusation, and at most $r-1$ cases of both being said to be knight (as the 2 rogues may or may not team up to deceive the princess).

Looking at the distribution of cases "both say the other is knight" and "at least one rogue accusation", we can identity if the person being examined is a knight or rogue.

If I am to brute force, then I can do $O(n)$ queries for each person, giving $O(n^2)$ time.

But I am uncertain how to do divide and conquer here.

I can eliminate dividing naively into $\frac{n}{2}$ sizes, because the distribution of knights and rogues will no longer follow the initial more than $\frac{n}{2}$ knights.

One idea I have is, initially pick one person j and do the pairing with $n-1$ others to see if he is knight or rogue. If he is knight then we're done.
If he is rogue, then we can know which in the previous results must be rogues. The o

An efficient algorithm using stack

• Initialize an empty stack.

• For each person $p$ in the given people:

• If the stack is empty, push $p$ to the stack.

• Otherwise, pit $p$ against the person at the top of the stack.

• If both say the other one is a knight, either both are knights or both are rogues. Push $p$ to the stack.

• Otherwise, at least one of them is a rogue. Pop the stack once.

• Return the person at the top of the stack.

The time-complexity of the algorithm is $O(n)$.

The space-complexity of the algorithm is $O(1)$ if we can reuse the input array as a stack.
Two Exercises

Exercise 1 (easy). Explain why all people in stack at the end are knights.

Exercise 2 (easy). Suppose the number of knights is equal to the number of rogues instead. Show that it is impossible to find a knight for sure in the worst case.

StackExchange Computer Science Q#150164, answer score: 10