@rahul, they are right as binary search is made on sorted array only.
think of array as
0,2,3,8, 10, 12, 14., 15. here a[mid ] = 10 > mid(4) hence next search
should happen between 0 till 4 subarrray.. In my code the input array
is also not correct as it is not a sorted array and that's why I made
a mistake in writing the code as well. Anyways we are clear and
concluded the code as final as below
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);
else
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 8:15 PM, rajul jain <[email protected]> wrote:
> i think he is wrong bcoz this array in not sorted one.
> so solution of Ankit is right.
>
> On Thu, Mar 3, 2011 at 7:33 PM, nishaanth <[email protected]> wrote:
>>
>> Ignore the previous post..there is a small error in the code..
>> @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);
>> else
>> 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;
>> }
>> 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.
>
> --
> 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.
