PuTtA EaSY Solution C++ ✅ | Beats 96% 🔥🔥 Binary Search |
Intuition\n Describe your first thoughts on how to solve this problem. \nBinary Search\n\n\n# Complexity\n- Time complexity:O(logn)\n Add your time complexity h
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBinary Search\n\n\n# Complexity\n- Time complexity:$$O(logn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        int left = 0;\n        int n = nums.size()-1;\n        int right = n;\n        while(left<=right){\n            int mid = left+(right-left)/2;\n            //edge case, if mid is single element\n            if((mid == 0 || nums[mid] != nums[mid-1]) &&( mid == n || nums[mid] != nums[mid+1] )) return nums[mid];\n        //as size of nums is odd logic to find which side to move\n        int leftpart;\n        if(nums[mid] == nums[mid-1])\n        leftpart = mid-1;\n        else leftpart = mid;\n        \n        if(leftpart%2 == 1) right = mid-1;\n        else left = mid+1;\n\n        }\n        return 0;\n    }\n};\n```
['Binary Search', 'C++']