Link

Medium Binary Search

Amazon

Facebook

Google

Microsoft

2020-05-12

540. Single Element in a Sorted Array

Question:

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly 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.


Solution:

Find the closest even number near middle, if nums[middle] != nums[middle + 1], it means the target value is on the left side. Otherwise, it will be on the right side.

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