Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.

Example 1:

Input: [1,1,2,3,3,4,4,8,8]Output: 2

 

Example 2:

Input: [3,3,7,7,10,11,11]Output: 10

 

Note: Your solution should run in O(log n) time and O(1) space.

 

1 public class Solution { 2     public int singleNonDuplicate(int[] nums) { 3         int left = 0, right = nums.length - 1; 4          5         while (left <= right) { 6             if (left == right) return nums[left]; 7              8             int mid = left + (right - left) / 2; 9             if (mid > 0 && mid < right && nums[mid] != nums[mid - 1] && nums[mid] != nums[mid + 1])10                 return nums[mid];11             12             if (mid > 0 & nums[mid - 1] == nums[mid]) {13                 if ((mid - left) % 2 == 1) left = mid + 1;14                 else right = mid - 2;15             } else if (mid <= right && nums[mid] == nums[mid + 1]) {16                 if ((mid - left) % 2 == 1) right = mid - 1;17                 else left = mid + 2;18             }19         }20         return -1;21     }22 }