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.

Follow up: Your solution should run in O(log n) time and O(1) space.

 

Example 1:

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:

Input: nums = [3,3,7,7,10,11,11]
Output: 10

 

 1 class Solution {
 2     public int singleNonDuplicate(int[] nums) {
 3         if (nums == null || nums.length == 0) {
 4             throw new IllegalArgumentException("invalid input.");
 5         }
 6         int start = 0;
 7         int end = nums.length - 1;
 8         while (start < end) {
 9             int mid = start + (end - start) / 2;
10             // 如果是偶数，表明从mid-1总共有偶数个数。如果mid和mid+1对应的数相等，那么左边部分是好的。
11             if (mid % 2 == 0) {
12                 if (nums[mid] == nums[mid + 1]) {
13                     start = mid + 2;
14                 } else {
15                     end = mid;
16                 }
17             } else {
18                 // 如果是奇数，表明从0-mid总共有偶数个数。如果mid和mid-1对应的数相等，那么左边部分是好的。
19                 if (nums[mid] == nums[mid - 1]) {
20                     start = mid + 1;
21                 } else {
22                     end = mid;
23                 }
24             }
25         }
26         return nums[start];
27     }
28 }