public int findCelebrity(int n) {
int c = divide(0, n1);
if (c == 1) return 1;
for (int i = 0; i < n; i++)
if (i != c && knows(c,i)) return 1;
return c;
}
public int divide(int l, int h) {
if (h <= l) return l;
int m = (l + h) / 2;
return select(divide(l, m), divide(m+1, h));
}
private int select(int c1, int c2) {
if (c1 == c2) return c1;
else if (c1 == 1) return c2;
else if (c2 == 1) return c1;
else if (knows(c1,c2)) return c2;
else if (knows(c2,c1)) return c1;
else return 1;
}
BONUS 3liner!!! :) Inspired by czonzhu's solution.
@czonzhu has a good explanation of his 2 iterations approach. For those who are interested in how I transformed it into Java's streaming solution:
 In the first iteration we look at 1 to n1 (inclusive) people in the party. We initialize our iteration assuming that person 0 is the celebrity. Then we check if person i knows c. If true, then c is still likely to be a celebrity, otherwise we swap c and i and suppose i is the celebrity.

In Java 8 IntStream is simply a sequence of integers.

Adding the modifier 'range' to it specifies the range of the integers.

Adding the modifier 'forEach' includes the logic that has to be performed for every element i in the defined range.
 Now that we have our candidate c from the first iteration we want to confirm that he/she is indeed the celebrity. We iterate over all people in range 0 to n1 (inclusive). For each person we check if this person is not a c (to avoid knows(c,c) which will always return true) and whether he/she doesn't know our candidate celebrity c or c knows i. If any of this conditions is true then our candidate c is not a celebrity.

Similarly to the previous step we create an IntStream of given range.

Adding the modifier 'filter' removes all elements that do not satisfy the filtering condition (described above).

If At least one person satisfies our filtering condition, i.e. disconfirms that c is a celebrity, we leave this person in the stream. Therefore, when we perform a count() on the stream we get the number of people who invalidated that c is a celebrity. If this count is > 0 we return 1, otherwise c is confirmed to be a celebrity.
A quick note, c in this case is a global field because streams in Java 8 can only use final or effectively final variables. Local variables of the method will not work because when the method is popped off the stack the local variables are dereferenced.
private int c = 0;
public int findCelebrity(int n) {
IntStream.range(1,n).forEach(i > c = knows(i,c) ? c : i);
return IntStream.range(0,n).filter(i > c != i && (knows(c,i)  !knows(i,c))).count() > 0 ? 1 : c;
}