Find the unduplicated element in a sorted array

Yes, you can use the sortedness to reduce the complexity to O(log n) by doing a binary search.

Since the array is sorted, before the missing element, each value occupies the spots 2*k and 2*k+1 in the array (assuming 0-based indexing).

So you go to the middle of the array, say index h, and check either index h+1 if h is even, or h-1 if h is odd. If the missing element comes later, the values at these positions are equal, if it comes before, the values are different. Repeat until the missing element is located.

Do a binary "search" (rather traversal) on the array, check both neighbors, if both are different from the value in the middle, you have the solution. This is O(log n).