The force deduction method summarizes the single elements in the 540 ordered array

Original link ： Power button

describe ：

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

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/single-element-in-a-sorted-array
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
* logN The complexity of must be binary search , Judgment in middle Before or after . If even and odd digits are equal , Then after , Otherwise, it was before .

Code ：

public class Solution540 {
    public int singleNonDuplicate(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int left = 0;
        int right = nums.length - 1;
        int middle;
        int target = 0;
        while (left <= right) {
            middle = (left + right) / 2;
            if (middle % 2 == 0) {
                if (middle < nums.length - 1 && nums[middle] == nums[middle + 1]) {
                    left = middle + 1;
                } else {
                    right = middle - 1;
                    target = middle;
                }
            } else {
                if (nums[middle] == nums[middle + 1]) {
                    right = middle - 1;
                    target = middle;
                } else {
                    left = middle + 1;

                }
            }
        }
        return nums[target];
    }
}