LeetCode 540. Single Element in a Sorted Array

原题链接在这里：https://leetcode.com/problems/single-element-in-a-sorted-array/

题目：

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.

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.

题解：

When doing binary search, if mid is odd, mid minus 1, as we want to get the first value of pair.

Compares nums[mid] with nums[mid+1].

If they are not equal, single must be on its left, r = mid.

If they are equal, this is a pair, single must be on its right, l = mid + 2.

Eventually return nums[l].

Time Complexity: O(logn). n = nums.length.

Space: O(1).

AC Java:

 1 class Solution {
 2     public int singleNonDuplicate(int[] nums) {
 3         int l = 0;
 4         int r = nums.length - 1;
 5         while(l < r){
 6             int mid = l + (r - l) / 2;
 7             if(mid % 2 == 1){
 8                 mid--;
 9             }
10
11             if(nums[mid] != nums[mid + 1]){
12                 r = mid;
13             }else{
14                 l = mid + 2;
15             }
16         }
17
18         return nums[l];
19     }
20 }

类似Find Minimum in Rotated Sorted Array.