```
/* The knows API is defined in the parent class Relation.
boolean knows(int a, int b); */
public class Solution extends Relation {
public int findCelebrity(int n) {
int c = find(0, n - 1);
for (int i = 0; i < n; i++) {
if (i == c) {
continue;
}
if (knows(c, i) || !knows(i, c)) {
return -1;
}
}
return c;
}
private int find(int lo, int hi) {
if (lo == hi) {
return lo;
}
int mid = (lo + hi) / 2;
int left = find(lo, mid);
int right = find(mid + 1, hi);
if (knows(left, right)) {
return right;
}
return left;
}
}
```