@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 <anandut2...@gmail.com> 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 <harishp...@gmail.com> 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 > > <jalaj.jaiswa...@gmail.com>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 algoge...@googlegroups.com. > >> To unsubscribe from this group, send email to > >> algogeeks+unsubscr...@googlegroups.com<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 algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com<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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.