no the order is log(n)
On Wed, Mar 4, 2009 at 4:45 PM, sharad kumar <[email protected]> wrote: > but commplexity is O(n2) rite??wat about my solution?? > > On Wed, Mar 4, 2009 at 4:32 PM, Prakhar Jain <[email protected]> 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 <[email protected]> wrote: >> > >> > @Prakhar how would you ensure that this is highest index >> > >> > On Mar 1, 3:05 pm, Prakhar Jain <[email protected]> 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 >> >> <[email protected]> wrote: >> >> >> >> > cout << ((int)((int*)upperbound(a,a+5,k)-a))/4-1; >> >> >> >> > 2009/3/1 sharad kumar <[email protected]> >> >> >> >> >> #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 >> >> >> <[email protected]> >> >> >> 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 <[email protected]> >> >> >>> 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 >> >> > > > > > -- Prakhar --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
