Single Element in a Sorted Array

Problem

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.

Solution

Binary Search Solution: O(lg n) time

public class Solution {
    public int singleNonDuplicate(int[] nums) {
        int start = 0, end = nums.length - 1;
        while (start < end) {
            int mid = (start + end) / 2;
            if (mid % 2 == 1) mid--;
            if (nums[mid] != nums[mid + 1]) end = mid;
            else start = mid + 2;
        }
        return nums[start]; //return nums[end] is fine too 
    }
}

Analysis

We solve this problem by thinking about its indices
The nums is given by only one element appearing once and all other appearing twice
Therefore, the length must be odd
Then we apply Binary Search and get pair of nums from the middle
The index of first number should be even and index of the second should be odd
Hence we decrement mid-- if its odd
Then if nums[mid] != nums[mid + 1], we know that single element appears before in this range
Hence, we move the end to mid
Otherwise, we move to the right by setting start = mid + 2
At the end, we return nums[start]