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 <[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 > > > > -- ---------------------------------------- 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 [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 -~----------~----~----~----~------~----~------~--~---
