540. Single Element in a Sorted Array

// LeetCode URL: https://leetcode.com/problems/single-element-in-a-sorted-array/

/**
 * Binary Search
 *
 * Consider a1, a1, a2, a2, a3, a4, a4, a5, a5. Since the input array is sorted,
 * single element will always be on the even index. On the left of single
 * element, the pairs will be (even, odd). On the right of single element, the
 * pairs will be (odd, even).
 *
 * Time Complexity: O(log N)
 *
 * Space Complexity: O(1)
 */
class Solution {
    public int singleNonDuplicate(int[] nums) throws IllegalArgumentException {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("Invalid Input");
        }

        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            // The first element of the middle pair should be at an even index if the left
            // part is sorted.
            int mid = left + (right - left) / 2;
            if (mid % 2 != 0) {
                mid--;
            }

            // Found a pair. The single element must be on the right.
            if (nums[mid] == nums[mid + 1]) {
                left = mid + 2;
            } else {
                // Did not find a pair. The single element must be on the left.
                right = mid;
            }
        }

        // 'left' should always be at the beginning of a pair.
        // When 'left > right', left must be the single element.
        return nums[left];
    }
}