Code Complexity Misunderstanding of Single Element in a Sorted Array

43 Views Asked by At

The problem which is on LeetCode says that

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.

Return the single element that appears only once.

Your solution must run in O(log n) time and O(1) space.

Example 1:

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2
Example 2:

Input: nums = [3,3,7,7,10,11,11]
Output: 10

My friend said that leetcode has accepted it as one of its right solution as you can see below image. However, I can't understand how the code is O(logn). Could you explain me? I assert that the code is of O(n) because it iterates through one by on up to its size.

enter image description here

public class Solution {
    public int SingleNonDuplicate(int[] nums) {
            int result = nums[0];

            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] != result && i % 2 == 1)
                {
                    result = nums[i - 1];
                    return result;
                }
                else
                {
                    result = nums[i];
                }
            }

            return result;
    }
}
0

There are 0 best solutions below