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]
}
}