```
public class Solution {
public int singleNonDuplicate(int[] nums) {
// algorithm 2017/07/20: A smarter algorithm is to do a binary search
// check the middle number: if it is different from both left and right number, then the middle number is the result
// if it is the same as the number on one side, we just need to check how many numbers are on this side
/*
1 1 2 2 3
1 1 2 2 3 3 4
1 2 2 3 3
1 2 2 3 3 4 4
*/
int left = 0, right = nums.length-1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] != nums[mid-1] && nums[mid] != nums[mid+1]) {
return nums[mid];
} else if (nums[mid] == nums[mid-1]) {
// middle number is equal to the one on left
if (1 == mid % 2 ) {
left = mid + 1; // singleNumber is on the right
} else {
right = mid - 2; // singleNumber is on the left. -2 because mid and mid-1 are same
}
} else {
// middle number is equal to the one on right
if (1 == mid % 2) {
right = mid - 1; // singleNumber is on the left
} else {
left = mid + 2; // single number is on the right
}
}
}
return nums[left]; // lower bound
}
```

}