⭐ Binary Search - Time Complexity + Space Complexity + Explanation ⭐
Time Complexity - Binary search takes O(logN base 2) time.\nSpace Complexity - Space taken is O(1).\nExplanation - To solve this problem, we use a modified vers
Time Complexity - Binary search takes O(logN base 2) time.\nSpace Complexity - Space taken is O(1).\nExplanation - To solve this problem, we use a modified version of binary search.\nWe know that mid is our target element, if the element is not equal to either its next or previous element (since array is sorted array).\nIf our mid isn\'t the target element, we need to search the left/right part of the array.\n\nIn an array where every element appears twice (1, 1, 2, 2) will always have an even number of elements.\nIn such an array, any element at an odd index is equal to the element at its previous index.\nHowever, an array with 1 non-repeated element will always have an odd number of elements.\nIn such an array, we can easily identify where the non-repeated element lies based upon whether our mid element satisfies this property.\n\nSatisfying either (mid is odd and nums[mid] == nums[prev]) or (mid is even and nums[mid] == nums[next]) means that all elements to the left of mid are in pairs - so we should search to its right.\n*Example:*\n[1, 1, 2, 2, 3, 4, 4]\n 0  1  2  3  4  5  6\n \nmid = 3, nums[mid] = 2\nmid doesn\'t hold our target element since arr[mid] = arr[prev], thus we need to move left/right.\nWe know mid is an odd index, and this is a result of having only elements which are in pairs to the left of mid.\nHence we should search to the right of mid for our target element.\n \n[1, 1, 2, 2, 3]\n 0  1  2  3  4 \n  \n mid = 2, nums[mid] = 2\n mid doesn\'t hold our target element since arr[mid] = arr[next], thus we need to move left/right.\n We know mid is an even index, and this is a result of having only elements which are in pairs to the left of arr[next].\n Hence we should search to the right of mid for our target element.\n \n ```\n class Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums){\n        int n = nums.size(), start = 0, end = n - 1, mid, next, prev;\n        if(n == 1) return nums[0];\n        while(start <= end){\n            mid = start + (end - start) / 2;\n            next = (mid + 1) % n;\n            prev = (mid + n - 1) % n;\n            if(nums[mid] != nums[prev] && nums[mid] != nums[next]) return nums[mid];\n            else if((mid % 2 && nums[mid] == nums[prev]) || (!(mid % 2) && nums[mid] == nums[next])) start = mid + 1;\n            else end = mid - 1;\n        }\n        return -1;\n    }\n};\n```\n\nKindly upvote if you found the solution helpful :)\n**For more such explanations of LeetCode problems along with their C++ solutions:**\nhttps://github.com/Arya-Gupta/LeetCode
['Array', 'C', 'Binary Tree', 'C++']