Java Binary Search O(lgN) : clear, easy, explained, no tricks
First, the code:\njava\npublic class Solution {\n    public int singleNonDuplicate(int[] nums) {\n        int n = nums.length;\n        int lo = 0, hi = n;\n   
First, the code:\n```java\npublic class Solution {\n    public int singleNonDuplicate(int[] nums) {\n        int n = nums.length;\n        int lo = 0, hi = n;\n        while (lo < hi) {\n            int mid = lo + (hi - lo) / 2;\n            if ((mid % 2 == 0 && mid + 1 < n && nums[mid] == nums[mid + 1]) ||\n                (mid % 2 == 1 && mid - 1 >= 0 && nums[mid] == nums[mid - 1]))\n                lo = mid + 1;\n            else\n                hi = mid;\n        }\n        return nums[lo];\n    }\n}\n```\nThe logic behind this is very easy: for each `mid`, we try to find understand whether the single number is on the **left** half. The `if` header tests that *`nums[mid]` is not single and neither is anything on its left*.\n* if `mid` is even, then there are `2m` numbers on the left of `mid`. For the statement of *`nums[mid]` is not single and neither is anything on its left* to hold, we need the `2m` numbers to the left of `mid` to be `m` pairs, and also `nums[mid]` be in a pair with `nums[mid + 1]`. Indeed, we only have to make sure in this case that `nums[mid], nums[mid + 1]` is a pair. You can prove by contradiction that as long as this holds, the sole single number can\'t be on the left of `mid`. Now that the statement of *`nums[mid]` is not single and neither is anything on its left* is proven, we can just go to the right half.\n* if `mid` is odd, then to prove *`nums[mid]` is not single and neither is anything on its left*, we only need to prove that `nums[mid - 1], nums[mid]` is a pair. `mid - 1` is even, and as long as `nums[mid - 1], nums[mid - 1 + 1]` forms a pair, we can actually use the argument of previous paragraph to prove that no entry to the left of `mid` is single. And neither is `mid` itself obviously. With *`nums[mid]` is not single and neither is anything on its left* proven, we can again to the right half.\n* If *`nums[mid]` is not single and neither is anything on its left* not provable, then go to left half since the single number is there.\n\nI am not entirely sure the above explanation suffices, but I do hope it helps.
[]