277 find the celebrity

https://leetcode.com/problems/find-the-celebrity/

/* 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 left = 0;
        int right = n - 1;
        // 这里不像二分查找，left最后是可能end up等于right的，因为他们可能同时移动
        while (left + 1 < right) {
            boolean ab = knows(left, right);
            boolean ba = knows(right, left);
            
            if (ab && ba) {
                left++;
                right--;
            } else if (ab) {
                left++;
            } else {
                right--;
            }
        }
        boolean ab = knows(left, right);
        boolean ba = knows(right, left);
        if (ab || ba) {
            int idx = ab ? right : left;
            for (int i = 0; i < n; i++) {
                if (i == idx) {
                    continue;
                }
                if (!knows(i, idx) || knows(idx, i)) {
                    return -1;
                }
            }
            return idx;
        }
        return -1;
    }
}

这都能二分查找我是没想到的，但是最后还是要验证