LeetCode. 540. Single Element in a Sorted Array

[Problem] https://leetcode.com/problems/single-element-in-a-sorted-array/

In a sorted array, every value except the singleton appears exactly twice. Before the singleton, each pair starts at an even index; after it, the pair alignment shifts, so each pair starts at an odd index.

At each iteration, align mid to the even index at the start of a pair. If nums[mid] == nums[mid + 1], that pair is intact and the singleton is to its right. Otherwise, the pair is disrupted at or before mid, so the singleton is at or to its left. This keeps the search interval focused on the half containing the singleton.

The input is guaranteed to be nonempty, have odd length, and contain exactly one singleton. The loop converges to its index and returns its value. Binary search takes $O(\log N)$ time and $O(1)$ extra space.

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if ((mid & 1) == 1) mid--;
            if (nums[mid] == nums[mid + 1]) {
                low = mid + 2;
            } else {
                high = mid;
            }
        }
        return nums[low];
    }
}