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