C++ binary search


  • 6
    H
    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];
        }
    };
    

  • 1

    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];
        }
    

  • 0
    L

    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]

  • 1
    M

    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];
        }
    };
    

  • 0

    Awesome solution!


Log in to reply
 

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