Day 52 || Binary Search || Easiest Beginner Friendly Sol
Intuition of this Problem:\nSince every element in the sorted array appears exactly twice except for the single element, we know that if we take any element at 
# Intuition of this Problem:\nSince every element in the sorted array appears exactly twice except for the single element, we know that if we take any element at an even index (0-indexed), the next element should be the same. Similarly, if we take any element at an odd index, the previous element should be the same. Therefore, we can use binary search to compare the middle element with its adjacent elements to determine which side of the array the single element is on.\n\nIf the middle element is at an even index, then the single element must be on the right side of the array, since all the elements on the left side should come in pairs. Similarly, if the middle element is at an odd index, then the single element must be on the left side of the array.\n\nWe can continue this process by dividing the search range in half each time, until we find the single element.\n\n ***Another interesting observation you might have made is that this algorithm will still work even if the array isn\'t fully sorted. As long as pairs are always grouped together in the array (for example, [10, 10, 4, 4, 7, 11, 11, 12, 12, 2, 2]), it doesn\'t matter what order they\'re in. Binary search worked for this problem because we knew the subarray with the single number is always odd-lengthed, not because the array was fully sorted numerically***\n<!-- Describe your first thoughts on how to solve this problem. -->\n**NOTE - PLEASE READ APPROACH FIRST THEN SEE THE CODE. YOU WILL DEFINITELY UNDERSTAND THE CODE LINE BY LINE AFTER SEEING THE APPROACH.**\n\n# Approach for this Problem:\n1. Initialize two pointers, left and right, to the first and last indices of the input array, respectively.\n2. While the left pointer is less than the right pointer:\n    - a. Compute the index of the middle element by adding left and right and dividing by 2.\n    - b. If the index of the middle element is odd, subtract 1 to make it even.\n    - c. Compare the middle element with its adjacent element on the right:\n        - i. If the middle element is not equal to its right neighbor, the single element must be on the left side of the array, so update the right pointer to be the current middle index.\n        - ii. Otherwise, the single element must be on the right side of the array, so update the left pointer to be the middle index plus 2.\n1. When the left and right pointers converge to a single element, return that element.\n<!-- Describe your approach to solving the problem. -->\n\n# Code:\n```C++ []\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        int left = 0, right = nums.size() - 1;\n        while (left < right) {\n            int mid = (left + right) / 2;\n            if (mid % 2 == 1) {\n                mid--;\n            }\n            if (nums[mid] != nums[mid + 1]) {\n                right = mid;\n            } else {\n                left = mid + 2;\n            }\n        }\n        return nums[left];\n    }\n};\n```\n```Java []\nclass Solution {\n    public int singleNonDuplicate(int[] nums) {\n        int left = 0, right = nums.length - 1;\n        while (left < right) {\n            int mid = (left + right) / 2;\n            if (mid % 2 == 1) {\n                mid--;\n            }\n            if (nums[mid] != nums[mid + 1]) {\n                right = mid;\n            } else {\n                left = mid + 2;\n            }\n        }\n        return nums[left];\n    }\n}\n\n```\n```Python []\nclass Solution:\n    def singleNonDuplicate(self, nums: List[int]) -> int:\n        left, right = 0, len(nums) - 1\n        while left < right:\n            mid = (left + right) // 2\n            if mid % 2 == 1:\n                mid -= 1\n            if nums[mid] != nums[mid + 1]:\n                right = mid\n            else:\n                left = mid + 2\n        return nums[left]\n\n```\n\n# Time Complexity and Space 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)$$ -->
['Array', 'Binary Search', 'C++', 'Java', 'Python3']