but commplexity is O(n2) rite??wat about my solution??
On Wed, Mar 4, 2009 at 4:32 PM, Prakhar Jain <prakh...@gmail.com> wrote:
>
> I would call search()
> not binsearch()
> search() find any index and then iterates sequentially till the highest
> index.
>
> Prakhar
>
> On Wed, Mar 4, 2009 at 4:27 PM, Kapil <navka...@gmail.com> wrote:
> >
> > @Prakhar how would you ensure that this is highest index
> >
> > On Mar 1, 3:05 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
> > >
> >
>
>
>
> --
> Prakhar
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
