【leetcode】540. A single element in an ordered array

subject ：

540.  A single element in an ordered array 
 Give you an ordered array of integers only , Each of these elements will appear twice , Only one number will appear once .

 Please find and return the number that only appears once .

 The solution you design must meet  O(log n)  Time complexity and  O(1)  Spatial complexity .

 Example  1:

 Input : nums = [1,1,2,3,3,4,4,8,8]
 Output : 2
 Example  2:

 Input : nums =  [3,3,7,7,10,11,11]
 Output : 10
 
 Tips :

1 <= nums.length <= 105
0 <= nums[i] <= 105

Dichotomy thinking ：

1. mid and mid^1 Are the subscripts of two adjacent numbers （∵ When mid For even when , The number adjacent to it is mid+1=mid ^ 1; When mid In an odd number of , The number adjacent to it is mid-1=mid ^ 1）.
2. We just need to compare whether the two adjacent numbers are equal , If equal , What we are looking for x The subscript of is greater than mid, Then the left boundary moves to the right low=mid+1; If it's not equal , be x The subscript of is less than or equal to mid, Then the right boundary moves to the left high=mid.
3. Adjust the boundary and continue the binary search , Until the subscript is determined x Value .

class Solution {
    
    public int singleNonDuplicate(int[] nums) {
    
        /**  An operation  O(n) */
    // int num = 0;
    // for(int i : nums){
    
    // num ^= i;
    // }
    // return num;

    /**  Dichotomy ：O(log n) */
        int low = 0, high = nums.length - 1;
        while (low < high) {
    
            int mid = (high - low) / 2 + low;
            if (nums[mid] == nums[mid ^ 1]) {
    
                low = mid + 1;
            } else {
    
                high = mid;
            }
        }
        return nums[low];
    }
}