class Solution {
    public int singleNonDuplicate(int[] nums) {
        int lo = 0, hi = nums.length - 1;
 
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
 
            if (mid % 2 == 1) mid--;
 
            if (nums[mid] == nums[mid + 1]) {
                lo = mid + 2;
            } else {
                hi = mid;
            }
        }
        return nums[lo];
    }
 
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 1, 2, 2, 3, 3, 4, 5, 5};
        System.out.println("Single element: " + solution.singleNonDuplicate(nums));
    }
}
 

Y2xhc3MgU29sdXRpb24gewogICAgcHVibGljIGludCBzaW5nbGVOb25EdXBsaWNhdGUoaW50W10gbnVtcykgewogICAgICAgIGludCBsbyA9IDAsIGhpID0gbnVtcy5sZW5ndGggLSAxOwoKICAgICAgICB3aGlsZSAobG8gPCBoaSkgewogICAgICAgICAgICBpbnQgbWlkID0gbG8gKyAoaGkgLSBsbykgLyAyOwoKICAgICAgICAgICAgaWYgKG1pZCAlIDIgPT0gMSkgbWlkLS07CgogICAgICAgICAgICBpZiAobnVtc1ttaWRdID09IG51bXNbbWlkICsgMV0pIHsKICAgICAgICAgICAgICAgIGxvID0gbWlkICsgMjsKICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgIGhpID0gbWlkOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHJldHVybiBudW1zW2xvXTsKICAgIH0KCiAgICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKSB7CiAgICAgICAgU29sdXRpb24gc29sdXRpb24gPSBuZXcgU29sdXRpb24oKTsKICAgICAgICBpbnRbXSBudW1zID0gezEsIDEsIDIsIDIsIDMsIDMsIDQsIDUsIDV9OwogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiU2luZ2xlIGVsZW1lbnQ6ICIgKyBzb2x1dGlvbi5zaW5nbGVOb25EdXBsaWNhdGUobnVtcykpOwogICAgfQp9Cg==