Deep Explanation | Leetcode Official Solution | Visual | [Python]
Overview \n\nWe must find the only unique element in a sorted array where all two copies of all other elements exist (or duplicate) \n \nfirst let us make some 
### Overview \n\nWe must find the ***only unique*** element in a ***sorted array*** where all **two copies*** of all other elements exist (or duplicate) \n \nfirst let us make some key observtions about the problem \n\nassuming  the constraints of the problem hold true, if  there is a match for an element it always exists to the ***adajcent left*** or the ***adjacent right*** of that number; otherwise the number is ***unique***.\n\nObserve key observation 1 in ***Figure 1***\n\n![image](https://assets.leetcode.com/users/images/2becd6d2-77aa-443c-a50e-d80bbcc30941_1610678546.0418265.png)\n\n* * * \n\n\nRecall there are ***two copies*** of all elements ***except*** the unique value.\n\ninother words there are ***p*** pairs of ***duplicates*** where each pair is distinct. There is one value that cannot form a pair, this value is ***unique***. This means the length of the input array is ***2p + 1***\n\n***Observe key observation 2 in Figure 2***\n![image](https://assets.leetcode.com/users/images/6af86593-3e0b-4a18-b9eb-72a8e8a6818b_1610679299.535254.png)\n\n* * * \n\n***we know that a unique value can  only exist if the array is of odd length***. We can use this ***principle to search*** the array for the ***unique value***.  \n\nsince this array is sorted a binary search like approach may prove useful. if we repeatedly divide the array in half and leverage our search principle mentioned above, we can always find the unique value in ```O(log N)``` time and ```O(1)``` space.\n\nWe always look for the unique value in the half that is odd length. because the half that is odd length, has some number of pairs ***k***, and ***1 unique value***. the other half would contain only pairs \n\n* * * \n***The question now becomes, how do we do this?***\n* * * \n\nyou may have already noticed that if we section an array of odd length into two parts by a mid point, ***both halves will contain the same number of elements.***\n\n![image](https://assets.leetcode.com/users/images/83a68561-7ce5-4261-92da-b1280fbb0d0b_1610680461.5730007.png)\n\nRecall that we said our search criteria was to always visit the half that is of ***odd length*** until we find our unique value, but from what we just saw in ***Figure 3*** it seems like this is going to be problem.\n\n* in the first example in ***Figure 3***  there is ***neither*** the ***left*** or ***right half*** is of ***odd length***, both halves are ***even length***. \n\n* in the second example in ***Figure 3***  both the ***left*** and the ***right*** halves are of ***odd length***, so it is unclear which half should be searched next. \n\nif we combine our key observations from above with our search principle, a solution is possible. \n\n***we always check to see if the mid point is the unique value*** \n\n![image](https://assets.leetcode.com/users/images/4ead9ac1-5153-43b3-87f5-d669d98ad22c_1610682563.080835.png)\n\nwe can see the unique value lies in the left half. what happens next?\n\n![image](https://assets.leetcode.com/users/images/3534e7a2-fba5-42be-b5fe-c224053f5100_1610684170.6051178.png)\n\n\n\n\n\nfrom here we can see that the 4 cases mentioned in the leetcode official solution arise\n\n\n1. match is on ***left of mid point***  and both ****left and right halves*** are of ***even length***\n\t* exclude match and mid point and go left, that is ```high = mid - 2``` \t\n\n2. match is on ***left of mid point*** and both ***left and right halves*** are of ***odd length***\n\t\t* exclude match mid point and go right, that is ```low = mid + 1``` \t\n\n3. match is on ***right of mid point***  and both ****left and right halves*** are of ***even length***\n\t * exclude match and mid point and go right, that is ```low = mid + 2``` \n4.  match is on ***right of mid point*** and both ***left and right halves*** are of ***odd length***\n\t * exclude match mid point and go left, that is ```high = mid - 1``` \n\n\n ```python\n def singleNonDuplicate(self, nums: List[int]) -> int:\n        lo = 0\n        hi = len(nums) - 1   \n        while lo < hi:\n            mid = (lo + hi) // 2\n\t\t\t# look to right for pair \n            if nums[mid + 1] == nums[mid]:\n\t\t\t\t# both halves are even length,\n                if (hi - mid) % 2 == 0:\n                    lo = mid + 2\n                else:\n                    hi = mid - 1\n\t\t\t # look to left for pair \n            elif nums[mid - 1] == nums[mid]:\n\t\t\t\t# both halves are even length\n                if (hi - mid) % 2 == 0:\n                    hi = mid - 2\n                else:\n                    lo = mid + 1\n            else:\n\t\t\t\t# no pair on either side, must be unique \n                return nums[mid]\n        return nums[lo]\n```    \n\ncode courtesy of leetcode official solution \n\n\n\n\n\n\n    \n
['Binary Tree']