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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
// ============================================================================ // Author: Kenneth Perkins // Date: Nov 19, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find a single element in a sorted array // ============================================================================ public class Solution { public int SingleNonDuplicate(int[] nums) { var lo = 0; var hi = nums.Length - 1; while (lo < hi) { // Get the mipoint var mid = lo + (hi - lo) / 2; // Check to see if mid is even var isEven = mid % 2 == 0; // If mid is even, its duplicate should be the next index // If mid is odd, its duplicate should be the previous index if ((isEven && nums[mid] == nums[mid + 1]) || (!isEven && nums[mid] == nums[mid - 1])) { // Duplicate found, advance to next index. Single element is > mid lo = mid + 1; } else { // Pattern is broken. Single element is <= mid hi = mid; } } return nums[lo]; } }// http://programmingnotes.org/ |
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
Hi, I'm a software engineer. I write articles about programming and design in my spare time.
Leave a Reply