YES, you only need good invariant, initialy you put end=n to point outside the array and start=0 to point on the first element invariant is that start points to candidate solution, and that end points to element that cant be considered an answer
if you calculate mid=(start+end)/2, then it will never be mid==end,what is important, because you can use mid=(start+end+1)/2, what would not work you must not forget to check at the end if a[start]=k; start=0; end=n; while(start+1<end) { mid=(start+end)/2; if(a[mid]<=k) start=mid;else end=mid; } if(a[start]==k) cout<<start;else cout<<"no solution"; Someone my try to make modification so mid=(start+end+1)/2 will work, but please do not only use only mid as index. 2009/3/1 CHERUVU JAANU REDDY <jaanu.cher...@gmail.com> > 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 -~----------~----~----~----~------~----~------~--~---