@Anand,
It looks like your algorithm takes O(log N ) time.
Repeatedly choosing one half or the other half.
Similar to binary search.
Please correct me if I am worng.
-Thanks and regards,
Bujji.
On Jul 27, 12:29 am, Anand <[email protected]> wrote:
> *
> *
>
> *Using partition Logic of Quick Sort:
> *
>
> *Algoritm:*
>
> 1. pivot = 1st element.
> 2. Find the position of pivot in the array using partition logic of Quick
> sort
> 3. If Rank lies on the right side of the position then call this function
> with the right array
> 4. If rank lies on the left side of the position, then call this function
> with the left array.
> 5. If rank == position
> - return the element at position
>
>
>
> On Sun, Jul 25, 2010 at 4:44 AM, Algoose chase <[email protected]> wrote:
> > Add Each number from the stream to a Doubly linked list in sorted fashion
>
> > i = 1;
> > j = 1;
> > while( stream not empty)
> > {
> > if( i == 1&& j == 1)
> > {
> > Median = Cur ; /*Create New list with ist Number*/
> > }
> > Add_Node_In_Sorted_Order(Cur);
>
> > If( If new node is added after median )
> > i++; /*if the current median is 3rd node and new
> > node is added @ 5th position*/
> > bAddedBeforeMedian = False;
> > else
> > j++;
> > bAddedBeforeMedian = true;
>
> > if( i %2 == 1 && !bAddedBeforeMedian)
> > Median = median ->next;
> > else if (j%2==1 && bAddedBeforeMeidan)
> > Median = Median->prev
>
> > }
> > return Median->Data;
>
> > At any given point in time Median will point to the median among the
> > numbers seen so far
>
> > ---------------------------------------------------------------------------------------------
>
> > On Sat, Jul 24, 2010 at 8:02 PM, jalaj jaiswal
> > <[email protected]>wrote:
>
> >> You are given a stream of numbers which can be positive or negative. You
> >> are required to provide an operation FIND MEDIAN..which when invoked should
> >> be able return the median of the numbers in stream (in sorted order) in
> >> O(1)
> >> time.
>
> >> Eg: 0 1 2 3 4
> >> Right FIND MEDIAN returns 2 as median
>
> >> Now input is -2 -4
> >> So Stream = 0 1 2 3 -2 -2 -4
> >> Sorted Stream would be -4 -2 0 1 2 3 4 and FIND MEDIAN returns 1
>
> >> --
> >> With Regards,
> >> Jalaj Jaiswal
> >> +919026283397
> >> B.TECH IT
> >> IIIT ALLAHABAD
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to [email protected].
> >> To unsubscribe from this group, send email to
> >> [email protected]<algogeeks%2bunsubscr...@googlegroups.com>
> >> .
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> > [email protected]<algogeeks%2bunsubscr...@googlegroups.com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
>
> - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
