Ryan,
I wouldn't say you bombed it. Maybe a B-/C+. :)
Array.Copy is expensive on every insert. You can avoid that by
growing your array by a specified amount each time instead of +1 on
each insert. Hence the performance penalities you pay in .NET for a
poorly initialized collection.
The boundary checks for less than first or greater than last are
unnecessary and they don't help performance.
FWIW, look at a reference implementation. Take a look at how
SortedList etc is implemented in the CLR using Reflector.
The rest is form - binary search should be a separate function.
HTH
-Doug
On 10/7/05, Ryan Graham <[EMAIL PROTECTED]> wrote:
> 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(r) http://www.develop.com
>
> View archives and manage your subscription(s) at http://discuss.develop.com
>
===================================
This list is hosted by DevelopMentor® http://www.develop.com
View archives and manage your subscription(s) at http://discuss.develop.com
