c i tested it for all possibilities.it gives the largest index for
particular duplicate at both extreme boundaries.o(nlogn is a bit slow...
On Sun, Mar 1, 2009 at 4:44 PM, CHERUVU JAANU REDDY <jaanu.cher...@gmail.com
> wrote:
> if there are large number of duplicates then it takes long time...
> so we have to apply Binary search on rightside.
>
> On Sun, Mar 1, 2009 at 3:35 PM, Prakhar Jain <prakh...@gmail.com> wrote:
>
>>
>> I guess the Soln given is O(n)
>> Much better can be achieved through binary serach O(nlogn)
>>
>> int binsearch(int a[],int start,int end,int key)
>> {
>> int mid=(start+end)/2;
>> if(start==end && a[mid]!=key)
>> return -1;
>> if(a[mid]>key)
>> end=mid;
>> else if(a[mid]<key)
>> start=mid;
>> else
>> return mid;
>> }
>>
>> int search(int a[],int key,int n)
>> {
>> int p=binsearch(a,0,n,key)
>> if(p>=0)
>> while(a[p]==key)
>> p++;
>> return p-1;
>> }
>>
>> On Sun, Mar 1, 2009 at 3:14 PM, Miroslav Balaz <gpsla...@googlemail.com>
>> wrote:
>> >
>> > cout << ((int)((int*)upperbound(a,a+5,k)-a))/4-1;
>> >
>> > 2009/3/1 sharad kumar <aryansmit3...@gmail.com>
>> >>
>> >> #include<iostream.h>
>> >> int main()
>> >> {
>> >> int a[5]={3,3,3,6,7};
>> >> int k;
>> >> cin>>k;
>> >> int i=0,j=1,c=0;
>> >> for(;i<5;i++)
>> >> {
>> >> if(a[j-1]!=a[i]&& a[i]!=k)
>> >> j++;
>> >> else
>> >> c=i;
>> >> }
>> >> cout<<c;
>> >> return 0;
>> >> }
>> >>
>> >> On Sun, Mar 1, 2009 at 9:50 AM, sharad kumar <aryansmit3...@gmail.com>
>> >> wrote:
>> >>>
>> >>> hi,
>> >>> does the above solution need any time complexity and space complexity
>> in
>> >>> specifific. idont understand use binary search
>> >>> On Sun, Mar 1, 2009 at 12:13 AM, jaanu <jaanu.cher...@gmail.com>
>> wrote:
>> >>>>
>> >>>> Given a sorted arrays of N integers, possibly with duplicates, write
>> a
>> >>>> function that
>> >>>> returns the highest index of an element X in that array if found or
>> -1
>> >>>> otherwise.(use Binary search)
>> >>>>
>> >>>>
>> >>>
>> >>
>> >>
>> >>
>> >
>> >
>> > >
>> >
>>
>>
>>
>> --
>> Prakhar
>>
>>
>>
>
>
> --
>
>
>
>
> ----------------------------------------
> CHERUVU JAANU REDDY
> M.Tech in CSIS
>
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
