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