# C++ binary search

• ``````class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int n = nums.size(), left = 0, right = n - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (mid % 2 == 0) {
if (nums[mid] == nums[mid-1]) right = mid - 2;
else if (nums[mid] == nums[mid+1]) left = mid + 2;
else return nums[mid];
}
else {
if (nums[mid] == nums[mid-1]) left = mid + 1;
else if (nums[mid] == nums[mid+1]) right = mid - 1;
}
}
return nums[left];
}
};
``````

• I like your solution, seems to have the fewest cases of the ones I've seen, most clean. This is a simple problem in concept, but getting the conditionals correct takes some careful consideration.

I've translated to C#

``````    public int SingleNonDuplicate(int[] nums)
{
int n = nums.Length;
int left = 0;
int right = n - 1;

while (left < right)
{
int mid = left + (right - left) / 2;
if (mid % 2 == 0)
{
if (nums[mid] == nums[mid-1]) right = mid - 2;
else if (nums[mid] == nums[mid+1]) left = mid + 2;
else return nums[mid];
}
else
{
if (nums[mid] == nums[mid-1]) left = mid + 1;
else if (nums[mid] == nums[mid+1]) right = mid - 1;
}
}
return nums[left];
}
``````

• Here is my python version, the test is right, but the submission always go wrong, the FAQ says I should define a global /static variable but

def init(self):
self.nums=[]

it doesn't work?
anyone knows why?

``````class Solution(object):

def singleNonDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
#for i in nums:
#   if nums.count(i)==1:
#      return i
lo = 0
hi = len(nums)-1
while lo < hi:
mid = lo + (hi-lo)/2 # equals to mi=(lo+hi)/2
if nums[mid] % 2 == 0:
if  nums[mid]==nums[mid-1]:
hi=mid-2
elif nums[mid]==nums[mid+1]:
lo=mid+2
else:
return nums[mid]
else:
if nums[mid]==nums[mid-1]:
lo=mid+1
elif nums[mid]==nums[mid+1]:
hi=mid-1

return nums[lo]``````

• The code can be simplified a bit:

Using examples to see how the binary search works:

size 9 array:
2 2 5 5 7 7 8 8 9
1 2 2 5 5 7 7 8 8

size 7 array:
2 2 3 3 5 5 7
1 2 2 3 3 5 5

Walk through these 4 examples and you will know how the code works. Note that the single number index must be 0, 2, 4, 6, ... etc and cannot be 1, 3, 5, ...

``````class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int l = 0, r = nums.size()-1;
while(l < r) {
int m = l + (r-l)/2;
if(m%2==0) {
if(nums[m]==nums[m+1]) l=m+2;
else r=m;
}
else {
if(nums[m]==nums[m-1]) l=m+1;
else r=m-1;
}
}
return nums[l];
}
};
``````

• Awesome solution!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.