[Figure] Use example as your guide: generalization
\nIntuition:\nSorted array!\nThat suggests we can use binary search.\nThen I will use classical binary search template: [low_index, high_index)\nThe middle valu
\n**Intuition:**\nSorted array!\nThat suggests we can use binary search.\nThen I will use classical binary search template: [low_index, high_index)\nThe middle value are highlighted in red color.\n\nThere is some observation about potential place for the unique item: it must be in an even-indexed position\n![image](https://assets.leetcode.com/users/codedayday/image_1589322173.png)\n\nNote, for original middle value of ex3 and ex4, the middle indices need to be decreased by 1 and converted in ex3\u2019, and ex4\u2019 respectively. The unique number, highlighted in green, must occupied an even-index position.\n\nOne more fun knowledge about i-th index in zero-index space is that i means there are i items have smaller indices then current i-th item:\nFor example,\nnums[i]\nmeans there are i items are in the left of nums[i].\nWhat does it mean to this question?\nOkay, if some index, say, mid,  is even, then it means there are even number of items in the left of the mid.\n\n```\nclass Solution {//BEST: binary search\npublic://Time/Space: O(logN); O(1)\n    int singleNonDuplicate(vector<int>& nums) {\n        const int n = nums.size();\n        int lo = 0, hi = n;\n        if(n==1) return nums[0];\n        while(lo<hi){\n            int mid = lo + (hi - lo) / 2;\n            if(mid%2 == 1) mid--; //  if mid%2 == 1; then at least two items are there.\n            if(nums[mid] == nums[mid+1]) // left and current duet are all alright\n                lo = mid +2;  // then move right by two positions.\n            else hi = mid;  // note, mid is even index, a potential home for unique number\n        }\n        return nums[lo];\n    }\n};\n\n\n```
[]