# Leetcode Q540

:::info
Contributor: [蘇炳立 (BillySu)](https://github.com/Billy4195)
:::

Problem:
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

### Solution 1:
Because the given array is sorted, the simplest way to solve this problem is to scan over the array to find the single element.
If a element is not the single element in the array, there is exact the same element next to it.
The pseudo code should be:

total_len = len(nums)
prev = None

if total_len == 1:
    return nums[0]

for idx in range(total_len):
    if nums[idx] != prev and nums[idx] != nums[idx+1]:
        return nums[idx]
    else:
        prev = nums[idx]
return nums[-1]

### Solution 2:
The best solution to solve this problem using only O(log(n)) time complexity, and this is also the requirement of this problem.
Since the complexity is log(n), it could be associated with binary search.

To solve this problem in log(n), we need to eliminate half of current candidates in each iteration.
1. We reduce the search range iteratively, so we need two Vars to store the start and the end point of current search range, the initial value is the start and the end of the given array
2. Check the middle point is the single element or not? if yes, then return this element, if No, then go to the step3
3. Check the element equal to the middle is on left-side or right-side
4. Check the length of remaining left part and right part is odd
5. Check the odd length part as the new start and the new end point

start_pt = 0
end_pt = len(nums) - 1

while start_pt <= end_pt:
    mid = (start_pt + end_pt) // 2
    if nums[mid] != nums[mid+1] and nums[mid] != nums[mid-1]:
        return nums[mid]
    
    if nums[mid] == nums[mid+1]:
        right_remain = end_pt - (mid + 1)
        if right_remain % 2:
            start_pt = mid + 2
        else:
            end_pt = mid -1
    else:
        left_remain = (mid - 1) - start_pt
        if left_remain % 2:
            end_pt = mid - 2
        else:
            start_pt = mid + 1
    
return nums[start_pt]