Shabz
BAN USERDo a left favored binary search for "1" and keep shrinking the window of search till you can't find and more 1s or search index of 1 remains same
public static int First1Search(int[] array)
{
int left = 0;
int right = array.Length - 1;
int minIndex = -1;
while (true)
{
int elementIndex = LeftFavoredSearch(array, left, right);
if (elementIndex == -1 || elementIndex == minIndex)
{
return minIndex;
}
else
{
minIndex = elementIndex;
right = minIndex;
}
}
}
public static int LeftFavoredSearch(int[] array, int l, int r)
{
if (l > r)
{
return -1;
}
int mid = (l + r) / 2;
if (array[mid] == 1)
{
return mid;
}
int leftSearch = LeftFavoredSearch(array, l,mid-1);
if (leftSearch != -1)
{
return leftSearch;
}
else
{
return LeftFavoredSearch(array, mid+1, r);
}
}
Use the combination of Array and HashTable
- Shabz August 26, 2013Insert
Insert the element in trailing tail of the array, insert the element as key in Hashtable and value as tail index of array , increment the tail index
Delete
Lookup the item index from hashtable, swap it with the tail -1 element of array, decrement the tail and remove the element from hash table
Random
Genrate any random value between the range of 0 to tail -1 of array and return that element
Lookup,
trivial
every operation is O(1)
D