@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 <[email protected]>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 <[email protected]> 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 <[email protected]>
>> 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 <[email protected]>
>> 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 <[email protected]>
>> 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 [email protected].
>> >> > To unsubscribe from this group, send email to
>> >> > [email protected].
>> >> > 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 [email protected].
>> >> To unsubscribe from this group, send email to
>> >> [email protected].
>> >> 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 [email protected].
>> > To unsubscribe from this group, send email to
>> > [email protected].
>> > 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 [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
