EASY TO C++ SOLUTION || 540. Single Element in a Sorted Array Solved Medium Topics 
IntuitionThe problem is based on the observation that in a sorted array where every element appears twice except for one, the position of elements can help us d
# Intuition\n\nThe problem is based on the observation that in a sorted array where every element appears twice except for one, the position of elements can help us determine which half of the array to search. The key insight is that pairs of identical elements will always be positioned in such a way that their indices will either both be even or both be odd. When you encounter an index that does not conform to this pattern, it indicates that the single non-duplicate element lies in that half of the array.\n\n\n# Approach\n\n1. Initial Checks:\n   - If the array size is 0 or 1, return the only element (if present).\n   - Check if the first or last elements are the unique element (if they do not match their adjacent elements).\n2. Binary Search:\n   - Use a binary search approach to efficiently locate the single non-duplicate element.\n   - Initialize low to 1 and high to n-2 to avoid boundary issues while checking adjacent elements.\n   - Calculate mid as the average of low and high.\n   - Check if nums[mid] is different from both its neighbors (nums[mid - 1] and nums[mid + 1]). If so, return nums[mid].\n   - Determine which half of the array to search next:\n      - If mid is odd and nums[mid] matches nums[mid - 1], it indicates that the unique element must be in the right half. Thus, set low = mid + 1.\n      - If mid is even and nums[mid] matches nums[mid + 1], it also indicates that the unique element must be in the right half. Again, set low = mid + 1.\n      - Otherwise, search in the left half by setting high = mid - 1.\n3. End Condition:\n   - The loop continues until low exceeds high, ensuring all possibilities are covered.\n\n# Complexity\n- Time complexity:O(logn), The algorithm uses binary search which divides the search space in half at each step, leading to logarithmic time complexity.\n\n- Space complexity: O(1), The algorithm uses a constant amount of extra space for variables (low, high, and mid), regardless of the input size.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        int n = nums.size(), low = 1,high = n-2;\n\n        if(n == 0 || n == 1) return nums[0]; //singe element array\n        if(nums[0] != nums[1]) return nums[0]; //last element in array\n        if(nums[n-1] != nums[n-2]) return nums[n-1];\n\n        while(low <= high){\n            int mid = (low + high)/2;\n\n            if(nums[mid] != nums[mid - 1] && nums[mid] != nums[mid + 1]) return nums[mid];\n\n            //chcek for left half\n            if(((mid % 2 == 1) && (nums[mid] == nums[mid - 1])) || ((mid % 2 == 0) && (nums[mid] == nums[mid + 1]))){\n                low = mid + 1;  //eliminate the left half\n            }\n            //we are in the right half\n            else high = mid - 1; //eliminate the right half\n        }\n        return -1;\n    }\n};\n```
['Array', 'Binary Search', 'C++']