Java Binary Search, short (7l), O(log(n)) w/ explanations
All credits go to @Penghuan who thought of using the pairs wisely.\n\nThis method seems to be a bit simpler to understand, since it doesn't start with the left 
All credits go to [@Penghuan](/post/175763) who thought of using the pairs wisely.\n\nThis method seems to be a bit simpler to understand, since it doesn't start with the left half and stays a little bit closer to the conventional solutions.\n\n```\n   public static int singleNonDuplicate(int[] nums) {\n        int start = 0, end = nums.length - 1;\n\n        while (start < end) {\n            // We want the first element of the middle pair,\n            // which should be at an even index if the left part is sorted.\n            // Example:\n            // Index: 0 1 2 3 4 5 6\n            // Array: 1 1 3 3 4 8 8\n            //            ^\n            int mid = (start + end) / 2;\n            if (mid % 2 == 1) mid--;\n\n            // We didn't find a pair. The single element must be on the left.\n            // (pipes mean start & end)\n            // Example: |0 1 1 3 3 6 6|\n            //               ^ ^\n            // Next:    |0 1 1|3 3 6 6\n            if (nums[mid] != nums[mid + 1]) end = mid;\n\n            // We found a pair. The single element must be on the right.\n            // Example: |1 1 3 3 5 6 6|\n            //               ^ ^\n            // Next:     1 1 3 3|5 6 6|\n            else start = mid + 2;\n        }\n\n        // 'start' should always be at the beginning of a pair.\n        // When 'start > end', start must be the single element.\n        return nums[start];\n    }\n```
[]