540 Single Element in a Sorted Array

540. Single Element in a Sorted Array

1. Question

Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.

Example 1:

Input: [1,1,2,3,3,4,4,8,8]

Output: 2

Example 2:

Input: [3,3,7,7,10,11,11]

Output: 10

Note:Your solution should run in O(log n) time and O(1) space.

2. Implementation

(1) Binary Search

思路：用二分法的思想，中点mid，有三种情况 1. 如果nums[mid - 1] == nums[mid], 判断mid - 2 + 1(因为数组从0开始)是否奇数，如果是，则出现一次的数在[start, mid - 2]之间，否则在[mid + 1, end]之间

1. 和情况一类似，如果nums[mid] == nums[mid + 1] ，判断mid - 1 + 1是否奇数，是的话则答案在[start, mid - 1]之间，否则在[mid + 2, end]之间

2. 情况三，当nums[mid] != nums[mid - 1] 且 nums[mid] != nums[mid + 1]时，nums[mid]就是我们要找的数

public class Solution {
    public int singleNonDuplicate(int[] nums) {
        if (nums == null || nums.length <= 2) {
            return -1;
        }

        int start = 0, end = nums.length - 1, mid = 0;

        while (start + 1 < end) {
            mid = start + (end - start) / 2;

            if (nums[mid - 1] == nums[mid]) {
                if ((mid - 2 + 1)  % 2 != 0) {
                    end = mid - 2;
                }
                else {
                    start = mid + 1;
                }
            }
            else if (nums[mid] == nums[mid + 1]) {
                if ((mid - 1 + 1) % 2 != 0) {
                    end = mid - 1;
                }
                else {
                    start = mid + 2;
                }
            }
            else {
                return nums[mid];
            }
        }

        if (start > 0 && nums[start - 1] != nums[start]) {
            return nums[start];
        }
        else {
            return nums[end];
        }
    }
}

3. Time & Space Complexity

Binary Search: 时间复杂度O(logn), 空间复杂度O(1)