Daily Archives: November 19, 2021

C# || How To Find Single Element In A Sorted Array Using C#

The following is a module with functions which demonstrates how to find a single element in a sorted array using C#.


1. Single Non Duplicate – Problem Statement

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


2. Single Non Duplicate – Solution

The following is a solution which demonstrates how to find a single element in a sorted array.

The idea of this solution is the following:

Suppose we have the following array: [1,1,2,2,3,3,4,4,6,8,8]

We can observe that for each pair:

  • The first pair element takes the even array index position
  • The second pair element takes the odd array index position

For example, when examining the number 1 as a pair, we see it takes the array index positions 0 and 1.

Similarly for all other pairs, the first pair element takes the even array index position, and the second pair element takes the odd array index position.

Using this idea, we can see that this pattern for pairs will break when a single element appears in the array.

In this solution, we use binary search to look for the point in the array where the pattern mentioned above for the pairs first breaks

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:


2
10