Best C++✅Solution💥||Beats 87%🔥||Intuition Explained✅||O(logn)TC||O(1) SC
Follow Daily Dose of DSA Blog where I post important DSA Questions and different approaches for solving it!!!\nhttps://legolas12.hashnode.dev/\n\n\n# Intuition 
Follow Daily Dose of DSA Blog where I post important DSA Questions and different approaches for solving it!!!\nhttps://legolas12.hashnode.dev/\n![Single Element in a Sorted Array - LeetCode - Google Chrome 21-02-2023 16_04_47.png](https://assets.leetcode.com/users/images/5f33b65e-2be7-4693-8ee4-0611376ab373_1676975767.743381.png)\n\n# Intuition \nAs we all know the element can be found by binary search. But to decide the region we have to write the check function .Lets assume the required element is in the right region. Then we have two cases \n1) mid is 1st element in the pair\n2) mid is 2nd element in the pair\n\n1st case: if mid is 1st element in the pair and required singleton element is in right region. Then left of mid has even number of elements (present in pairs) \n2nd case: if mid is 2nd element in the pair and required singleton element is in the right region . Then left of mid has odd number of elements (elements in pair + pair of mid)\nwhile checking mid is even or odd be aware of the 0 based indexing which will reverse the meaning of even and odd.  \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nMade two check functions . Check 1 for checking mid has dissimilar elements to the right and left , if present return mid.\nI have written Check 2 if the element is present in the right region.\nand remaining all cases are covered in else statement.\n\n\nBasic Intuition for writing this check function is written above\nThen finally wrote BS code with this two check functions . Corner cases are handled seperately.\n```\nbool check(vector<int> &nums , int x )\n    {\n        if(nums[x]!=nums[x+1] && nums[x]!=nums[x-1])\n        {\n            return true;\n        }\n        else return false;\n    } \n\nbool check2(vector<int> &nums , int x)\n    {\n        if((nums[x]==nums[x+1] && x%2==0) || (nums[x]==nums[x-1] && x%2!=0))\n        {\n            return true;\n        }\n        else return false;\n    }\n```\n\n# Complexity\n- Time complexity: O(logn)\n\n\n- Space complexity:O(1)\n\n\n# Code\n```\nclass Solution {\npublic:\n\n    bool check(vector<int> &nums , int x )\n    {\n        if(nums[x]!=nums[x+1] && nums[x]!=nums[x-1])\n        {\n            return true;\n        }\n        else return false;\n    } \n\n    bool check2(vector<int> &nums , int x)\n    {\n        if((nums[x]==nums[x+1] && x%2==0) || (nums[x]==nums[x-1] && x%2!=0))\n        {\n            return true;\n        }\n        else return false;\n    }\n    int singleNonDuplicate(vector<int>& nums) \n {\n        int n =(int)nums.size();\n       \n        int ans;\n        int low = 0 , high= n-1;\n         if(n==1) return nums[0];\n        if(nums[0]!=nums[1]) return nums[0];\n\n        if(nums[high]!=nums[high-1]) return nums[high];\n        while(low<high)\n        {\n            int mid = (low+high)/2;\n            if(check(nums,mid))\n            {\n               return nums[mid];\n            }\n            else if(check2(nums,mid))\n            {\n             low = mid+1;\n            }\n\n           else high=mid-1;\n        }\n     \n       return nums[low];\n}\n};\n```
['Binary Search', 'C++']