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/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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
