I totally bombed this question in an interview so I'm posting my answer here
for comments and suggestions... perhaps (god help me) I'm just not that
bright, but this works and seems to be fairly efficent. The idea was simple,
insert an integer into a list that has already been sorted.
private int[] _list;
...
public void Insert(int value)
{
int[] tempArray;
// check for special cases
if (this._list == null)
{ // first item added create new array
this._list = new int[1];
this._list[0] = value;
return;
}
else if (this._list[this._list.Length-1] <= value)
{ // item to be added is greater than the last
// item in the array, append item to end
tempArray = new int[this._list.Length+1];
Array.Copy(this._list, tempArray, this._list.Length);
this._list = tempArray;
this._list[this._list.Length-1] = value;
return;
}
else if (this._list[0] >= value)
{ // item to be added is less than the first
// item in the array, insert item to the beginning
tempArray = new int[this._list.Length+1];
Array.Copy(this._list, 0, tempArray, 1, this._list.Length);
this._list = tempArray;
this._list[0] = value;
return;
}
int left = 0;
int right = this._list.Length;
int middle = 0;
int mod = 0;
// binary search loop
while (left <= right)
{
// modify the pivot point
middle = (left + right) / 2;
if (value > this._list[middle])
{ // item is greater than the pivot point
//Debug.WriteLine(value + " > " + this._list[middle]);
mod = 1;
left = middle + 1;
}
else if (value < this._list[middle])
{ // item is less than the pivot point
//Debug.WriteLine(value + " < " + this._list[middle]);
mod = 0;
right = middle - 1;
}
else
{ // item is equal to the pivot point
//Debug.WriteLine(value + " = " + this._list[middle]);
break;
}
}
// modify the pivot point again
middle += mod;
// rebuild array to allow space for new item
tempArray = new int[this._list.Length+1];
Array.Copy(this._list, 0, tempArray, 0, middle);
Array.Copy(this._list, middle, tempArray, middle+1, tempArray.Length -
(middle +1));
// insert new item
this._list = tempArray;
this._list[middle] = value;
}
===================================
This list is hosted by DevelopMentor® http://www.develop.com
View archives and manage your subscription(s) at http://discuss.develop.com
