This can be achieved by using Array.BinarySearch.
Prerequisite to read this FAQ
- Understanding of bitwise complement (also known as 1’s complement). The equivalent the bitwise complementoperator in C# is "~" (tilde) and in VB.NET “XOR”
In general we use Array.BinarySearch to find the element index in given array. But if you understand about return value of Array.BinarySearch function, we can build sorted array too. Even Microsoft used the same technic in implementing System.Collections.SortedList class.
Below is definition from MSDN about Array.BinarySearch return value:
The index of the specifiedvaluein the specifiedarray, ifvalueis found. Ifvalueis not found andvalueis less than one or more elements inarray, a negative number which is the bitwise complement of the index of the first element that is larger thanvalue. Ifvalueis not found andvalueis greater than any of the elements inarray, a negative number which is the bitwise complement of (the index of the last element plus 1).
It means, it returns the index of found element otherwise it returns the expected index position in bitwise complement.
Let’s see same thing in action. Below sample code (MySortedList class) acts like integer list and sorts its elements in ascending order dynamically whenever new element is added.
| Sample Code: MySortedList |
class Program
{
static void Main(string[] args)
{
MySortedList list = new MySortedList();
list.Add(10);
list.Add(8);
list.Add(7);
list.Add(7);
list.Add(20);
list.Add(16);
list.Add(1);
foreach (int v in list.Items)
{
Console.WriteLine(v);
}
Console.ReadLine();
}
} class MySortedList
{
int[] items = new int[0];
public int[] Items
{
get { return items; }
set { items = value; }
} public void Add(int value)
{
int index = Array.BinarySearch(items, value);
if (index < 0)
index = ~index; //Increase Items Array Size by 1
int lastIndex = items.Length;
int capacity = items.Length + 1;
int[] dupArray = new int[capacity];
Array.Copy(items, dupArray, items.Length);
items = dupArray; //Adjusting elements to insert element in its right index
if (index < lastIndex)
{
Array.Copy(items, index, items, index + 1, lastIndex - index);
}
items[index] = value;
}
} |
Output:
Download complete source code from here MySortedList.zip
I’m leaving the desending order implemetation for readers. But I want to leave the clue. It can achevied easily by using IComparer
