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