I should have mentioned that this problem only makes sense if the array values must be unique.
On Dec 6, 8:20 pm, Gene <gene.ress...@gmail.com> wrote: > You guys are working too hard. Think about the sequence of numbers > [ A[i] - i | i = 0,1,2,...n-1 ]. You are trying to probe this > sequence to find the number of zeros. If you think about it for a > while, you will see that this sequence is non-decreasing. It must be > a segment of zero or more negative numbers followed by a segment of > zero or more zeros followed by a segment of zero or more positive > numbers. Therefore you can easily use two binary searches to find the > index of the leftmost and rightmost zeros. This identifies all the > elements where A[i]=i in O(2 log n) = O(log n) time. Of course if the > searches fail, you have no elements at all where A[i]=i. > > On Dec 5, 9:46 am, Nikhil Agarwal <nikhil.bhoja...@gmail.com> wrote: > > > > > @Divesh I have updated my algo and Array A[1,2,3.....n] is sorted with > > unique elements.CALL FIND_EQUAL(A,1,n) > > > int FIND_EQUAL(A,start,end) > > 1.Go to the middle element > > 2. If A[mid]>mid) > > 3. if(start==mid) > > 4 return mid-1; > > 5 return FIND_EQUAL(A,1,mid-1); > > 6 if(A[mid]=mid) > > 7 if(mid==end) > > 8 return mid; > > 9 return FIND_EQUAL(A,mid+1,end); > > > On Sun, Dec 5, 2010 at 7:36 PM, coolfrog$ > > <dixit.coolfrog.div...@gmail.com>wrote: > > > > @Nikhil > > > run you algo .. > > > on test case > > > index -> 1 2 3 4 5 > > > value -> 1 2 3 4 5 > > > > ouput is mid+1= 3+1=4 > > > but it should be 5... > > > correct me if i am wrong... and u have assumed all are positive, hence > > > base index should be 1 > > > > On Sun, Dec 5, 2010 at 4:41 PM, Nikhil Agarwal > > > <nikhil.bhoja...@gmail.com>wrote: > > > >> If All the elements are unique and sorted in ascending order then we can > > >> design an algorithm for O(lgn) and all nos are positive. > > > >> Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements] > > > >> FIND_EQUAL(A,start,end) > > >> 1.Go to the middle element > > >> 2.If A[mid]==mid) > > >> return mid+1; > > >> if(A[mid]>mid) > > >> then FIND_EQUAL(A,start,mid-1) > > >> else > > >> FIND_EQUAL(A,mid+1,end) > > > >> Runs in O(lgn) > > > >> On Sun, Dec 5, 2010 at 12:20 PM, jai gupta > > >> <sayhelloto...@gmail.com>wrote: > > > >>> Any algorithm must in worst case lead to O(n) if the elements are not > > >>> unique. Take the case: > > >>> 1 2 3 4 5 6 > > >>> as all the elements satisfy the condition of of key==index . we must go > > >>> someway to each element. > > >>> Hence O(n). > > > >>> This may be somehow made less if the element are given to be unique by > > >>> using heap. > > > >>> -- > > >>> 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. > > > >> -- > > >> Thanks & Regards > > >> Nikhil Agarwal > > >> Senior Undergraduate > > >> Computer Science & Engineering, > > >> National Institute Of Technology, Durgapur,India > > >>http://tech-nikk.blogspot.com > > >>http://beta.freshersworld.com/communities/nitd > > > >> -- > > >> 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. > > > > -- > > > *Divesh* > > > (¨`·.·´¨) Always > > > `·.¸(¨`·.·´¨ ) Keep > > > (¨`·.·´¨)¸.·´Smiling! > > > `·.¸.·´" Life can give u 100's of reason 2cry,but u can give life > > > 1000's > > > > of reasons 2Smile" > > > > -- > > > 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. > > > -- > > Thanks & Regards > > Nikhil Agarwal > > Senior Undergraduate > > Computer Science & Engineering, > > National Institute Of Technology, > > Durgapur,Indiahttp://tech-nikk.blogspot.comhttp://beta.freshersworld.com/communitie... -- 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.
