540.single-element-in-a-sorted-array.md

540. Single Element in a Sorted Array

Clarification Questions

• No, it's clear from problem description.

Test Cases

Normal Cases

Input: nums = [1,1,3,4,4,5,5]
Output: 3

Edge / Corner Cases

• Single element is at the beginning or the end.

Input: nums = [5,6,6]
Output: 5

Input: nums = [6,6,7]
Output: 7

Binary Search

The array is sorted, the same number will be adjacent, so for every number that occurres twice, then the index and the number will be:

index: 0  1  2  3  4  5
array: 1, 1, 3, 3, 5, 5

The relation between the index and number is:

1. Index is even, then it should be the first number, it should be equal to the next number.
2. Index is odd, then it should be the second number, it should be equal to the previous number.

For the number that occurres once (4), the index and the number will be:

index: 0  1  2  3  4  5  6
array: 1, 1, 3, 3, 4, 5, 5

It breaks the relation between the index and the number, so we can use binary search to find the single number. (Similar idea of 278. First Bad Version)

index: 0  1  2  3  4  5  6
array: 1, 1, 3, 3, 4, 5, 5
       O  O  O  O  X  X  X
                   ^ // The first number that breaks the relation

fun singleNonDuplicate(nums: IntArray): Int {
    if (nums.size == 1) return nums[0]
    var left = 0
    var right = nums.size - 1
    while (left <= right) {
        val middle = left + (right - left) / 2
        // Index is odd, then it should be the second number.
        // Then it should be equal to the previous number.
        if (middle % 2 != 0) {
            if (middle - 1 >= 0 && nums[middle - 1] == nums[middle]) {
                left = middle + 1
            } else {
                right = middle - 1
            }
        } else {
            // Index is even, then it should be the first number.
            // Then it should be equal to the next number.
            if (middle + 1 < nums.size && nums[middle] == nums[middle + 1]) {
                left = middle + 1
            } else {
                right = middle - 1
            }
        }
    }
    return nums[left]
}

• Time Complexity: O(lg n).
• Space Complexity: O(1).