540.md

540. Single Element in a Sorted Array

Description

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

Thinking Process

1. Sorted array is usually associated with binary search technique, O(log n) requirement further confirms this intuition.
2. Using binary search to shrink the search space by half at each step. The side with the target is the side that contains odd number of items (excluding the partion point)

Code

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

Complexity

1. Time complexity is O(log n) by using binary search technique
2. Space complexity is O(1) since no addtional data structure is needed