題目： LeetCode - 540. Single Element in a Sorted Array

題目說明

給一個排序好的陣列，裡面只有一個值是單一存在的，其餘都兩兩成對，求單一存在的值為何？

※ 題目希望時間複雜度為 O(log n)

解題思路

觀察規則，使用二元搜尋法即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {             
        int begin = 0, end = nums.size(), mid;
        while(end - begin != 1)
        {
            mid = (begin + end) / 2;
            if(nums[mid - 1] != nums[mid] && nums[mid] != nums[mid + 1])
                return nums[mid];
            if(nums[mid - 1] != nums[mid] && nums[mid] == nums[mid + 1])
                if(mid % 2)
                    end = mid;
                else
                    begin = mid + 2;
            else if(nums[mid - 1] == nums[mid] && nums[mid] != nums[mid + 1])
                if(mid % 2)
                    begin = mid + 1;
                else
                    end = mid - 1;
        }
        return nums[begin];
    }
};