leetcode讲解--540. Single Element in a Sorted Array

题目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: 2Example 2:Input: [3,3,7,7,10,11,11]Output: 10Note: 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]; } }}