Java Binary Search with Detailed Explanation
Let's start with two simple observations.\n\nExample 1: An array with length 2*4 + 1\nleft = 0, right = 8, mid = 4.\nIf the single element X is on the left hand
Let's start with two simple observations.\n\n**Example 1**: An array with length ```2*4 + 1```\n```left = 0```, ```right = 8```, ```mid = 4```.\nIf the single element ```X``` is on the left hand side, ```nums[mid] == nums[mid-1]```: \n```[1, 1, X, 2, 2(mid), 3, 3, 4, 4]```\nIf the single element ```X``` is on the right hand side, ```nums[mid] == nums[mid+1]```: \n```[1, 1, 2, 2, 3(mid), 3, X, 4, 4]```\n\n**Example 2**: An array with length ```2*3 + 1```\n```left = 0```, ```right = 6```, ```mid = 3```.\nIf the single element ```X``` is on the left hand side, ```nums[mid] == nums[mid+1]```: \n```[1, 1, X, 2(mid), 2, 3, 3]```\nIf the single element ```X``` is on the right hand side, ```nums[mid] == nums[mid-1]```: \n```[1, 1, 2, 2(mid), 3, 3, X]```\n\nIn general, for an array with length ```2*n + 1```, if ```n``` is even, the behavior of ```mid``` will be the same as that in Example 1. Otherwise, it will be as in Example 2.\n\nBelow is the solution.\n```\nclass Solution {\n    public int singleNonDuplicate(int[] nums) {\n        if(nums.length == 1) return nums[0];\n        \n        int len = nums.length;\n        int left = 0;\n        int right = len - 1;\n        \n        while(left <= right && left < len && right >= 0){\n            int mid = left + (right - left)/2;\n            \n            if((mid-1 >= 0 && nums[mid-1] == nums[mid]) || (mid + 1 < len && nums[mid+1] == nums[mid])){ // nums[mid] is not single\n                int currLen = right - left; // actual length - 1                \n                if((currLen/2) % 2 == 0){\n                    if(nums[mid-1] == nums[mid]){\n                        // The element is on the left hand side\n                        right = mid - 2; // Skip mid-1 and mid as we know they are not single\n                    }\n                    else{\n                        // The element is on the right hand side\n                        left = mid + 2;\n                    }\n                }\n                else{\n                    if(nums[mid-1] == nums[mid]){\n                        // The element is on the right hand side\n                        left = mid + 1; // Skip mid\n                    }\n                    else{\n                        // The element is on the left hand side\n                        right = mid - 1;\n                    }\n                }\n            }\n            else return nums[mid];\n        }\n        \n        return nums[left];\n    }\n}\n```
[]