题目
Given a sorted array consisting of only integers where every element appears twice except for one element which appears 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.
题目地址
讲解
二分查找，包含一个数的一边个数一定是奇数个。
java 代码
class Solution {
public int singleNonDuplicate(int[] nums) {
return binarySearch(nums, 0, nums.length-1);
}
private int binarySearch(int[] nums, int left, int right){
if(left==right){
return nums[left];
}
int mid = (left+right)/2;
if(nums[mid-1]==nums[mid]){
if((right-mid)%2==1){
return binarySearch(nums, mid+1, right);
}else{
return binarySearch(nums, left, mid-2);
}
}else if(nums[mid+1]==nums[mid]){
if((mid-left)%2==1){
return binarySearch(nums, left, mid-1);
}else{
return binarySearch(nums, mid+2, right);
}
}else{
return nums[mid];
}
}
}