@Ankit..your algm is O(n)...you should split the problem size to n/2 at every stage...rather you are again computing both the subarrays..
Here is the correct code... int BsearchElemEqualIndex (int *a, int start, int end) { int mid = (((end - start) >> 1) + start); if (a[mid] == mid) return a[mid]; else if (a[mid] != mid) { if (mid == start || mid == end) { return -1; } else { if(a[mid] < mid ) BsearchElemEqualIndex (a, start, mid); BsearchElemEqualIndex (a, mid + 1, end); } } } int _tmain(int argc, _TCHAR* argv[]) { int a[SIZE] = {5,9,3,8,1,2,6,7}; int x = BsearchElemEqualIndex (a, 0, SIZE); printf ("%d", x); system ("PAUSE"); return 0; } On Thu, Mar 3, 2011 at 7:20 PM, jagannath prasad das <jpdasi...@gmail.com>wrote: > @ankit sinha:i dont think the algo u wrote is o(logn).....its o(N) i guess > > > On Thu, Mar 3, 2011 at 7:05 PM, Ankit Sinha <akki12...@gmail.com> wrote: > >> @sukhmeet, as per the question, there is a unique value which satisfy >> a[i] = i in the array and written code captures that only. Else we >> need to modify if we are interested in all such values which statisfy >> the said condition. And also in that case looping around bsearch will >> not be a good idea.. it will be better to go for simple loop in o(n) >> time as every time mid calculation is also costly. I agreed to Arpit >> view point and accordingly did coding as preetika needed as per arpit >> comments. >> >> Cheers!! >> Ankit >> >> On Thu, Mar 3, 2011 at 6:53 PM, sukhmeet singh <sukhmeet2...@gmail.com> >> wrote: >> > what should be the answer for this: >> > if A={0,1,2,4,5} >> > 0 or 1 or 2 >> > On Thu, Mar 3, 2011 at 6:26 PM, Ankit Sinha <akki12...@gmail.com> >> wrote: >> >> >> >> Hi, >> >> >> >> Here is the code to do this using Bsearch in o(logn) time. >> >> >> >> int BsearchElemEqualIndex (int *a, int start, int end) >> >> { >> >> int mid = (((end - start) >> 1) + start); >> >> if (a[mid] == mid) >> >> return a[mid]; >> >> else if (a[mid] != mid) >> >> { >> >> if (mid == start || mid == end) >> >> { >> >> return -1; >> >> } >> >> else >> >> { >> >> BsearchElemEqualIndex (a, start, mid); >> >> BsearchElemEqualIndex (a, mid + 1, end); >> >> } >> >> } >> >> } >> >> >> >> int _tmain(int argc, _TCHAR* argv[]) >> >> { >> >> int a[SIZE] = {5,9,3,8,1,2,6,7}; >> >> int x = BsearchElemEqualIndex (a, 0, SIZE); >> >> printf ("%d", x); >> >> system ("PAUSE"); >> >> return 0; >> >> } >> >> >> >> Cheers, >> >> Ankit!!! >> >> >> >> On Thu, Mar 3, 2011 at 11:04 AM, Param10k <paramesh...@gmail.com> >> wrote: >> >> > There is a sorted array and you have to write a fn to find a number >> in >> >> > the array which satisfies >> >> > >> >> > A[i] = i ; where A is the array and i is the index... >> >> > >> >> > - Param >> >> > http://teknotron-param.blogspot.com/ >> >> > >> >> > -- >> >> > You received this message because you are subscribed to the Google >> >> > Groups "Algorithm Geeks" group. >> >> > To post to this group, send email to algogeeks@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. >> >> > >> >> > >> >> >> >> -- >> >> You received this message because you are subscribed to the Google >> Groups >> >> "Algorithm Geeks" group. >> >> To post to this group, send email to algogeeks@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. >> >> >> > >> > -- >> > You received this message because you are subscribed to the Google >> Groups >> > "Algorithm Geeks" group. >> > To post to this group, send email to algogeeks@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. >> > >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@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. >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@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. > -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.