一、题目
LeetCode-540. 有序数组中的单一元素
地址：https://leetcode-cn.com/problems/single-element-in-a-sorted-array/
难度：中等
给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
示例 1:
输入: [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:
输入: [3,3,7,7,10,11,11]
输出: 10
注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。
二、解题思路
本题要求O(log n)时间复杂度，很明显不能用暴力法，只能用二分查找。
我们首先将left和 right 指向数组首尾两个元素。然后进行二分搜索将数组搜索空间减半，直到找到单一元素（该元素与左右两边的都不相等）或者只有一个元素为止。
搜索空间减半，如何将数组减半呢，我们很容易发现，单元素所在区间个数是奇数。
例如:
[1,1,2,3,3,4,4,5,5]
[1,1,2,2,3,3,4]
因此，我们可以通过判断以nums[mid]，区分的两个区间的元素个数的奇偶来使得，搜索空间减半。
三、实现过程
c++
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int left = 0,right = nums.size() - 1;
while(left < right){
int mid = left + (right - left) / 2;
bool flag = (right - mid) % 2 == 0;
if(nums[mid-1] == nums[mid]){
if(flag){
right = mid -2;
}else{
left = mid + 1;
}
}else if(nums[mid+1] == nums[mid]){
if(flag){
left = mid + 2;
}else{
right = mid - 1;
}
}else{
//单元素
return nums[mid];
}
}
return nums[left];
}
};
PHP
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function singleNonDuplicate($nums) {
$left = 0;
$right = count($nums) - 1;
while($left < $right){
$mid = (int)($left + ($right - $left)/2);
$flag = ($right - $mid) % 2 == 0;
if($nums[$mid-1] == $nums[$mid]){
if($flag){
$right = $mid -2;
}else{
$left = $mid + 1;
}
}else if($nums[$mid+1] == $nums[$mid]){
if($flag){
$left = $mid + 2;
}else{
$right = $mid - 1;
}
}else{
return $nums[$mid];
}
}
return $nums[$left];
}
}
JavaScript
/**
* @param {number[]} nums
* @return {number}
*/
var singleNonDuplicate = function(nums) {
var left = 0,right = nums.length - 1,mid;
while(left < right){
mid = Math.floor(left + (right - left)/2);
var flag = (right - mid) % 2 == 0;
if(nums[mid-1] == nums[mid]){
if(flag){
right = mid -2;
}else{
left = mid + 1;
}
}else if(nums[mid+1] == nums[mid]){
if(flag){
left = mid + 2;
}else{
right = mid - 1;
}
}else{
return nums[mid];
}
}
return nums[right];
};
四、小结
二分查找的基本思想并不能，难点在于如何找到合适的条件来使区间减半。
