C# Binary Search Explained
Approach\n1. if there\'s only one element return it\n2. check if the unique element is the first or last element of the array\n\nCASE 1: element at mid and mid 
# Approach\n1. if there\'s only one element return it\n2. check if the unique element is the first or last element of the array\n\n**CASE 1**: element at mid and mid - 1 are equal; \n    - get count of left array and check if it is even or odd\n    - in case it is even, discard and search **right**\n    - in case of odd, continue search on the **left** side\n\n**CASE 2**: element at mid and mid + 1 are equal; get right count\n\nto decide the direction of search check which part of the array has odd number of elements.\n\nif number of element from start to mid is odd then unique element will be present on this left side of the array else search on the right side.\n\n# Complexity\n- Time complexity: ```O(log n)```\n\n- Space complexity: ```O(1)```\n\n# Code\n```\npublic class Solution {\n    public int SingleNonDuplicate(int[] nums) {\n        int start = 0, end = nums.Length - 1;        \n        if(nums.Length == 1) return nums[end];\n\n        // if the unique element is the first or last element of the array\n        if(nums[0] != nums[1]) return nums[0];\n\n        // if the unique element is the last element of the array\n        if(nums[end] != nums[end - 1]) return nums[end];\n\n        while(start <= end) { \n            int mid = start + (end - start) /2;\n            if(nums[mid] != nums[mid - 1] && nums[mid] != nums[mid + 1])\n                return nums[mid];\n\n            if(nums[mid] == nums[mid - 1]) {\n                int leftCount = mid - start + 1;\n                if(leftCount % 2 == 0) start = mid + 1;\n                else end = mid - 2; \n            }\n            else if(nums[mid] == nums[mid + 1]) {\n                int rightCount = end + mid - 1;\n                if(rightCount % 2 == 0) end = mid - 1;\n                else start = mid + 2;\n            }\n        }\n        return -1;\n    }\n}\n```
['Binary Search', 'C#']