2022.02.14 - 239. A single element in an ordered array

1. subject

2. Ideas

(1) Two points search

• In an array where elements appear in pairs , The first subscript of each pair of elements is an even number , The second subscript is odd .
• When the middle subscript is an even number , If this element is equal to the next element , It means that the previous elements appear in pairs ; When the middle subscript is an odd number , If this element is equal to the previous element , It means that the previous elements appear in pairs .

3. Code

public class Test {
    
    public static void main(String[] args) {
    
    }
}

class Solution {
    
    public int singleNonDuplicate(int[] nums) {
    
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
    
            int mid = left + ((right - left) >> 1);
            if ((mid & 1) == 0) {
    
                if (nums[mid] == nums[mid + 1]) {
    
                    left = mid + 1;
                } else {
    
                    right = mid;
                }
            } else {
    
                if (nums[mid] == nums[mid - 1]) {
    
                    left = mid + 1;
                } else {
    
                    right = mid;
                }
            }
        }
        return nums[left];
    }
}