一：解题思路
这个题目如果采用之前单身数字那个题目的方法来做，时间复杂度为O(n)。但题目的要求是O(log(n))，所以不能采用哪种方法。
这个题目可以采用二分搜索的思想来做，对于数组中的任意一个数字，1.要么等于它左边的数字，2.要么等于它右边的数字，3.要么即不等于左边的数字，又不等于它右边的数字，这个时候就是单身数字。
Time:O(log(n)),Space:O(1)
二：完整代码示例 (C++版和Java版)
C++:
class Solution { public: int singleNonDuplicate(vector<int>& nums) { int low = 0, high = nums.size() - 1; while (low <= high) { int mid = low + (high-low) / 2; if (mid - 1 >= 0 && nums[mid] == nums[mid - 1]) mid--; else if (mid + 1 < nums.size() && nums[mid] == nums[mid + 1]) {} else return nums[mid]; if ((mid - low) % 2 == 1) high = mid - 1; else low = mid + 2; } return -1; } };
Java:
class Solution { public int singleNonDuplicate(int[] nums) { int low=0,high=nums.length-1; while(low<=high) { int mid=low+(high-low)/2; if(mid-1>=0 && nums[mid]==nums[mid-1]) mid--; else if(mid+1<nums.length && nums[mid]==nums[mid+1]){} else return nums[mid]; if((mid-low)%2==1) high=mid-1; else low=mid+2; } return -1; } }
原文：https://www.cnblogs.com/repinkply/p/12660554.html