Visually Explained, Binary Search Solution.
\u200B\nMain points from Question :\n It\'s been stated that elements appear exactly twice except for one element which is to be found.\n  Solution must run in 
\u200B\n**Main points from Question :**\n* It\'s been stated that elements appear exactly twice except for one element which is to be found.\n*  Solution must run in O(log n) time and O(1) space.\n\u200B\n**Intuition developed :**\n*   So from what we can discern from the given inputs that the inputs will be same for every two elements from start and increasing after as array is sorted.\n*   As it\'s sorted, binary search should be the first go to logic.\n\u200B\n**Main Solution :**\n\n*  The approach is simple. We take middle element and compare it to it\'s adjacent elements. \n* How we compare the middle element can be divided into two ways based on the following intuition:\n1. The elements will be in pair so every two elements will be common among value ideally.\n2. So, using that logic the 0\'th and 1\'th index will be same ideally if they aren\'t the element to be found.\n3. So, we can form a pair of two elements having common values.\n\n* Now, how we can use this in our approach? We take the middle element and check if it is even or not. \n1. If it\'s even, then we compare it to next element and check if they are equal or not.\n2. If they are equal that would mean in the array before that there is no single elemenet becaue if there was then the indexes wouldn\'t be in pairs from start and our even index wouldn\'t be equal to odd index (0 and 1 taken into context). So we increment start by mid+2 because till mid+1 there can\'t be surely any element single.\n3. In the case of mid and mid+1 not being equal then  we decrement end to mid as single element would surely lie in before or at mid.\n4. In the case of middle element not being even, then it would mean that mid and mid+1 would be equal. So, in case they are, then we just increase start by mid+1 because of the earlier even and odd index logic explained in point 2.\n5. If the elements aren\'t equal for odd middle element then we decrement end to mid.\n* At the end, we return starting element with the breaking condition of the loop being end greater than start.\n\n*  **Visual Explanation**\n\n![image](https://assets.leetcode.com/users/images/9c83a162-6f75-408d-b9fb-93fee905e117_1708863665.334861.png)\n![image](https://assets.leetcode.com/users/images/38a54e4e-ee63-4d5e-a357-17237582b147_1708863853.282165.png)\n![image](https://assets.leetcode.com/users/images/d5f0a2a2-ca0e-417e-8a93-58ec7b2cc942_1708864050.3487914.png)\n![image](https://assets.leetcode.com/users/images/0a6bf103-ad10-4cd8-9aca-1dc89e83817d_1708864282.9269726.png)\n\n```\n    public int singleNonDuplicate(int[] nums) {\n        int start = 0;\n        int end = nums.length-1;\n        while(start <end){\n            int mid = start + (end - start)/2;\n            boolean isEven = mid%2==0;\n            \n            if(isEven){\n                if(nums[mid] == nums[mid+1]){\n                    start = mid+2;\n                }else{\n                    end = mid;\n                }\n            } else {\n                if(nums[mid] == nums[mid-1]){\n                    start = mid+1;\n                } else {\n                    end = mid-1;\n                }\n            }\n        }\n        return nums[start];\n    }\n```\n![image](https://assets.leetcode.com/users/images/b114a98e-a531-4f2d-b063-8575fdb043b7_1708662663.8377373.png)\n
['Binary Tree', 'Java']