May Leetcode Challenge

Single Element in a Sorted Array

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

Binary search, take mid of array
Mid not equal left or right, return it
Check elements count of left and right
With odd case, we can move to left if first left element equal to mid
With even case, we can move to right if first right element equal to mid

class Solution {
    func singleNonDuplicate(_ nums: [Int]) -> Int {
        var low = 0, high = nums.count - 1
        
        while low < high {
            var mid = (high + low) / 2
            if mid % 2 == 1 { mid -= 1 }
            
            if nums[mid] != nums[mid + 1] { 
                high = mid 
            } else{
                low = mid + 2
            }
        }
    
        return nums[low]
    }
}