Question 1: O(lg(n)) running time with binary search:

```
int missingNumber(vector<int>& nums) {
int lo = 0, hi = nums.size()-1;
while (lo < hi) {
int mid = (lo+hi)/2;
// We are left with 2 elements:
if (hi - lo + 1 < 3) break;
// Move mid to last element of same number:
while (mid+1 <= hi && nums[mid] == nums[mid+1]) mid++;
// If mid is at the end of the array we need to move it to the left:
if (mid == hi) {
while (nums[mid] == nums[mid-1]) mid--;
mid--;
}
// Recurse on half that doesn't have 3 * number of elements:
if ((mid-lo+1)% 3 == 0) {
// Right:
lo = mid+1;
} else {
// Left:
hi = mid;
}
}
return nums[lo];
}
```