C++ Binary Search Solution O(LogN)
Runtime: 4 ms, faster than 97.93% of C++ online submissions for Single Element in a Sorted Array.\nMemory Usage: 11.1 MB, less than 39.06% of C++ online submiss
Runtime: 4 ms, faster than 97.93% of C++ online submissions for Single Element in a Sorted Array.\nMemory Usage: 11.1 MB, less than 39.06% of C++ online submissions for Single Element in a Sorted Array.\n\n```\nWe can do binary search over the sorted array to find the single element. But on which condition we should\nmove to left half or right half ? During binary search we always make move decision  based on mid value,\nhere we do the same too but we consider both mid value and index and there are 4 possible cases:\n\n1. Mid Index Odd: \nMeans the length of array from start till mid value (included) is even. As the length of subarray [0, mid] is even\nthe single element can be in [0, mid] or [mid+1, n-1]. Subarray [0, mid] length is even and if all elements in\nsubarray are twice means no single element, then nums[mid] and nums[mid-1] will be same and single\nelement will be in the right half [mid+1, n-1], so we move to right half. Otherwise nums[mid]!=nums[mid-1]\nand there is a single element in the left half [0, mid] and  so we move to left half.\n\nExample:\n[1,1,2,3,3,5,5] => mid = 3 => nums[mid]!=nums[mid-1] => nums[3]!=nums[2] =>move to left half\n[1,1,2,2,3,5,5] => mid = 3 => nums[mid]==nums[mid-1] => nums[3]==nums[2] => move to right half\n\n2. Mid Index Even:\nMeans the length of array from start till mid value (included) is odd. As the length of subarray [0, mid] is\nodd the single element can be in [0, mid] or [mid+1, n-1]. Subarray [0, mid] length is odd and if nums[mid]\nand nums[mid+1] are same then the single element is in the right half, otherwise it is in the left half.\n\nExample:\n[1,1,3,2,2,4,4,5,5] => mid = 3 => nums[mid]!=nums[mid+1] => nums[3]!=nums[4] =>move to left half\n[1,1,2,2,4,4,5,6,6] => mid = 3 => nums[mid]==nums[mid+1] => nums[3]==nums[4]  =>move to right half\n```\n\n\n```\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        \n        int n = nums.size();\n        // base cases\n        if(n==1)return nums[0];\n        if(nums[n-1]!=nums[n-2])return nums[n-1];\n        if(nums[0]!=nums[1]) return nums[0];\n        \n        // iterative binary search\n        int left = 0;\n        int right = n-1;\n        int mid;\n        while(left<right)\n        {\n            int mid = left + (right-left)/2;\n            \n            // mid is odd means subarray [0,mid] length is even\n            // single element in the right half if nums[mid]==nums[mid-1], otherwise left half\n            if(mid % 2 ==1)\n            {\n                if(nums[mid]!=nums[mid-1])right = mid;\n                else left = mid + 1;                \n            }\n            // mid is even means subarray [0,mid] length is odd\n            // single element in the right half if nums[mid]==nums[mid+1], otherwise left half\n            else\n            {\n                if(nums[mid]!=nums[mid+1])right = mid;\n                else left = mid + 1;\n            }            \n        }\n        \n        // after binary search the left element will contain the single element\n        return nums[left];\n    }\n};\n```
['Array', 'C', 'Binary Tree']