Longer than writing my own binary search, but I wanted to see how this would look. I let `Collections.binarySearch`

search in a special `List`

object which returns `-1`

for indexes before the single element, `0`

for the index of the single element, and `1`

for indexes after the single element. So I run binary search for `0`

. Since my special `List`

object computes its entries only on the fly when requested, this solution takes O(log n) time and O(1) space.

```
public int singleNonDuplicate(int[] nums) {
List list = new ArrayList() {
public int size() {
return nums.length;
}
public Integer get(int index) {
if ((index ^ 1) < size() && nums[index] == nums[index ^ 1])
return -1;
if (index == 0 || index % 2 == 0 && nums[index - 1] != nums[index])
return 0;
return 1;
}
};
return nums[Collections.binarySearch(list, 0)];
}
```

A variation, the helper `isOff`

tells whether the index is in the part that's "off" (the single element and everything after it):

```
public int singleNonDuplicate(int[] nums) {
List list = new ArrayList() {
public int size() {
return nums.length;
}
public Integer get(int index) {
return isOff(index) + isOff(index - 1);
}
int isOff(int i) {
return i == size() - 1 || i >= 0 && nums[i] != nums[i ^ 1] ? 1 : 0;
}
};
return nums[Collections.binarySearch(list, 1)];
}
```